kadane’s algorithm

All you need is going through all sub-arrays, keep the global maximum and compare.

• O(n) runtime complexity
• O(1) space.

Following function shows the Kadane’s algorithm implementation which uses two variables, one to store the local maximum and the other to keep track of the global maximum:

1
2
3
4
5
6

def (A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

So we assume that the largest subarray is the first element, then we go through A[1:] elements (all elements except the first one).

At each step, what we do is:

• Can current element plus the last largest sum_ help to find a largest subarray (line 4)?
• If yes, update the max_ending_here or our local maximum, otherwise current element is the largest subarray (array of one).
• Then update the global maximum or max_so_far if there is a new global maximum.

When the loop is over, return the global maximum.