Maximum Subarray

By -
Problem Statement :

How to find the maximum sum of a sub array.
Example : for the array [1,2,-3,1] maximum sum possible is for the sub array [1,2] = 3.
                  for the array [10,5,-24,20,-1,35] maximum sum possible is for the sub array [20,-1,35]=54

Solution:  Kadane's Algorithm provides 0(n) solution to solve the problem. Kadane's algorithm keeps track of the maximum value of a sequence ending at the current point, and the maximum value seen so far.



Following Code sample demonstrates a method which can be used to find the maximum sub array.
public int getMaximumSubarray(int inputArray[]) {
  int max_ending_here = 0, max_so_far = 0;

  for (int i = 0; i < inputArray.length; i++) {
     max_ending_here = max(0, max_ending_here + inputArray[i]);
     max_so_far = max(max_so_far, max_ending_here);
  }
  return max_so_far;
 }

Comments

Post a Comment

Popular posts from this blog

Difference between volatile and synchronized

By -
volatile is a field modifier, while synchronized modifies code blocks and methods. So we can specify three variations of a simple accessor using those two keywords: int i1; int geti1() {return i1;} volatile int i2; int geti2() {return i2;} int i3; synchronized int geti3() {return i3;} geti1() accesses the value currently stored in i1 in the current thread . Threads can have local copies of variables, and the data does not have to be the same as the data held in other threads. In particular, another thread may have updated i1 in it's thread, but the value in the current thread could be different from that updated value. In fact Java has the idea of a "main" memory, and this is the memory that holds the current "correct" value for variables. Threads can have their own copy of data for variables, and the thread copy can be different from the "main" memory. So in fact, it is possible for the "main...
Read more

Converting Java Map to String

By -
Java Collections framework, String manipulation etc is something that we often encounter in Development process. For processing collections (like checking null/empty, Intersection, Disjunction) We do have some of the very use full libraries. Some of the Collection related libraries are Apche Commons Collections and Google  Collections(Guava). Problem Use Case This article explains how to convert a Java Map to String(and vice versa) using different libraries and technique. One way is to use StringBuilder(Or String) and loop though the Map and build the String by applying some sort of separator ( for key:value and entry). Here we have to take care of the null value etc. Without Any Library If we want to convert the map to a String with key value separator and also individual entry seperator in the resulting String, we have to write code for that. For a simple Map, we have to iterate though the map, take care of the null values etc. Following is...
Read more

Different ways to initialize arrays in java

By Sidd Bhattacharjee -
Different ways to initialize array's in java Array Initialization in Java Different ways to initialize array's in java Java Arrays can be populated in a number of ways following summarizes different options. One item at a time using a loop Following example we are declaring rolNumms array of size 10 and adding one item at a time using a for a loop. //Using For loops int rollNums[] = new int[10]; for (int i=0; i At the Time of Declaration We can set the content of the array while declaring the array it self. Both the syntax will result in initializing the array with 10 items. Note that when we provide the initializer while declaring the size of the array cannot be specified. int rollNums2[] = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9 ,10}; int rollNums3[] = {1, 2, 3, 4, 5, 6, 7, 8, 9 ,10}; Arrays.setAll() and Generator function We can set the content of the array using the Arrays.setAll() method as well. int rollNums4 [] = new int [10]; Arrays.setAll(rollNums4, p -> p ...
Read more