Kadane’s Algorithm

Given an array, find the greatest sum of a contiguous subset. For example, the input can be [3, 5, -9, 1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1, -5, 4] and the output should be 19 because the contiguous subset with the greatest sum is [1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1]

So conceptually, what’s the best approach to solving this problem? We need to create a function that iterates through each individual element and holds both the current running total as well as the overall maximum running total. Let’s call the current running total maxEndingHere and the overall max maxSoFar . In order to maximize maxEndingHere within each iteration, we need to check whether maxEndingHere should be equal to the current number or to the current number plus the previous maxEndingHere. In other words, within each iteration, maxEndingHere = Math.max(num, maxEndingHere + num) . To keep track of the overall max we must also update maxSoFar upon each iteration. It gets updated when maxEndingHere > maxSoFar or we could write maxSoFar = Math.max(maxEndingHere, maxSoFar) .

The overall solution will look like this:

In terms of space-time complexity, this runs in O(n) time and O(1) space.