Maximum Subarray Problem

Given an array of integers, find the largest sum of a contiguous subarray.

For example:

Input: [1, -1, 5, 3, -7, 4, 5, 6, -100, 4]

Output: 16 because the largest subarray in this example is [5, 3, -7, 4, 5, 6], and its sum is 5 + 3–7 + 4 + 5 + 6 = 16

The problem can be viewed in-depth here.

You may be thinking to iterate over each possible subarray, find their sums, and output the max sum, but in terms of time and space complexity, that’s just to much.

Brute Force Depiction

There’s actually a way to solve it in O(n) time. Kadane’s Algorithm may seem tricky at first, but it’s easy once you understand it.

The idea is, keep track of both a local maximum and a global maximum and compare it at each iteration. If the local maximum is ever greater than the global maximum, the global maximum should be equal to the local maximum.

Kadane’s Algorithm Depiction

The solution should look something like this:

Notice how after iterating, if the global maximum is less than zero, the greatest contiguous subarray is an empty array whose sum is zero.