Maximum Subarray Problem.

/*Kadane’s Algorithm solves the maximum subarray problem in O(N) time.

It scans through each element of the list, calculating the value of the maximum sum of any subarray ending at it.
It is either 0 or the element plus the sum ending at the previous index.

Python code:

def max_subarray(A):
max_so_far = max_ending_here = 0
for x in A:
max_ending_here = max(0, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
*/
public class Kadane
{
public static int seqStart=0, seqEnd=-1;
public static void main(String args[])
{
int[] a ={-2, 1, -3, 4, -1, 2, 1, -5, };
int max = max_subarray(a);
System.out.println("Max subsequence starts from " + seqStart +" and ends at " + seqEnd + " and the max is " +max);
}
private static int max_subarray(int[] a)
{
int maxSum =0, thisSum =0;
for(int i=0, j=0;j {
thisSum = thisSum + a[j];
if(thisSum > maxSum)
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
else if (thisSum < 0)
{
i = j+1;
thisSum = 0;
}
}
return maxSum;
}
}