Maximum Subarray Sum Problem using Kadane's Algorithm

This video explains how Kadane's Algorithm works for finding the maximum subarray sum. Kadane's Algorithm optimizes the code to run it in O(n) time complexity.

[gangar]

well explained!! Thanks! would be perfect if the variables used in the code were also named the same names given in the previous explanation.

[mmichaelid]

This fails to pass the test case for an array a = [ -500] though.. as it returns 0 instead of -500

This is the corrected Java implementation:

public static int maxSubArray(final List<Integer> a) {
int current_max = a.get(0);
int max_so_far = a.get(0);
for (int i = 1; i < a.size(); i++) {
current_max = Math.max(a.get(i), current_max + a.get(i));
max_so_far = Math.max(max_so_far, current_max);
}
return max_so_far;
}

[chandragarre]

shouldnt it be - current_max = max(A[i], current_max+A[i]) ?