**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.

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

Good One

ReplyDelete