Kadane's Algorithm – PatrickJackson.dev

Computer science history is all about building upon the work that came before us – “standing on the shoulders of giants” as it goes. Kadane’s Algorithm is no exception. And in this case it took fresh eyes just one minute to find an optimal solution to the Maximum subarray sum problem, where others had studied for months.

Maximum subarray Problem

The maximum subarray sum problem is defined as given an array A[1..n] find the maximum sum of any contiguous subarray of A.

Interestingly, this originates from 1977 when this problem was being examined with a 2d array in the form of digital images. The brute force solution for a 2d array is O(n⁶) – prohibitively slow. In order to gain insight, the problem was broken down to a 1d array and we have the problem examined in this post.

For more in-depth look into this algorithm and it’s interesting history, Programming Pearls has detailed an explanation.

The brute force solution for this problem – iterating through all the subarrays and then comparing sums – is a O(n³ ) time & space complexity. This was improved to O(n²) and then again to O(n log n).

This problem is only interesting if the array includes negative numbers, otherwise the solution is always the entire array. Consider the array below. What is the maximum subarray?

In this example the solution is [3, 2], because there is no other subarray with a sum greater than 5.

A brute force solution is simple and runs in O(n²) time:

/**
 * Bruteforce solution that uses nested loops
 * Time complexity: O(n²)
 * Space complexity: O(1)
 */
fun maxSubarraySumBruteForce(array: IntArray): Int {
    var maxSum = Integer.MIN_VALUE
    for (i in array.indices) {
        var subarraySum = 0
        for (k in i until array.size) {
            subarraySum += array[k]
        }
        if (subarraySum > maxSum) {
            maxSum = subarraySum
        }
    }
    return maxSum
}

Kadane attended a talk on the problem and the O(n log n) solution (not shown here), and devised a solution in minutes that ran in O(n) time.

His solution was not immediately obvious, however it was simple and only a few lines. It keeps the maxSoFar as it traverse the array. The maximum of all items up to the current item(maxEndingHere) is calculated by taking the maximum of the maxEndingHere and maxEndingHere + the current item. maxSoFar is then updated with the maximum of maxSoFar and maxEndingHere.

import kotlin.math.max

/**
 * Kadane's solution - computes in one pass
 * Time complexity: O(n)
 * Space complexity: O(1)
 */
fun maxSubarraySum(array: IntArray): Int {
    var maxEndingHere = 0
    var maxSoFar = 0

    array.forEach {
        maxEndingHere = max(it, maxEndingHere + it)
        maxSoFar = max(maxEndingHere, maxSoFar)
    }
    return maxSoFar
}

The full source code and tests in Kotlin and Java are available here.

Share on Facebook