Posts

Showing posts from December, 2013

Maximum Subarray

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; }