Photo by James Harrison on Unsplash

An Intuitive Explanation of Kadane’s Algorithm

Introduction

Feeling stuck on Kadane’s Algorithm? You came to the right place. Answering technical questions is a core part of the interview process for any coding job. One of the most common questions is the “max subarray sum” problem. You could use a brute force approach, but that won’t get you any points with the interviewer. (If it does, run!) There’s a much better way: Kadane’s algorithm.

In this article, I’ll teach you a simple way to understand Kadane’s algorithm.

What is the Max subarray sum problem?

Given an array A of integers, find the biggest sum for any contiguous (continuous) subarray in A. If all values in A are greater than or equal to 0, then the solution is the sum of all values in A.

Brute Force Approach

First, I’ll explain the brute force approach and its flaws. Take a look at this array:

[1, -2, 3, -4, 5, -3, 2, 2, 2]

If we were to use a brute force approach to find the largest sum of any contiguous subarray in A, we would do the following:

1. Given A, declare a variable: max_sum = A[0].
2. Go over every index i in A.
3. For each zero-based index, find the maximum sum of each possible contiguous subarray that has a length from 1 to i+1, and whose last value is at index i.

For example:

[1, -2, 3, -4, 5, -3, 2, 2, 2]

The biggest contiguous array that can be made at i=0 is [1]. The sum of that contiguous subarray is 1 and max_sum = 1.

[1, -2, 3, -4, 5, -3, 2, 2, 2]

Now we go to i=1 and have a subarray [1, -2]. The sum of this contiguous subarray is -1 and max_sum = 1.

[1, -2, 3, -4, 5, -3, 2, 2, 2]

Now we have a contiguous subarray of length 1 at i=1. The sum of this array is -2 and max_sum = 1.

Lets skip ahead to i = 4 and see what that looks like:

[1, -2, 3, -4, 5, -3, 2, 2, 2] >>> subarray=[5]

[1, -2, 3, -4, 5, -3, 2, 2, 2] >>> subarray: [-4, 5]

[1, -2, 3, -4, 5, -3, 2, 2, 2] >>> subarray: [3, -4, 5]

[1, -2, 3, -4, 5, -3, 2, 2, 2] >>> subarray: [-2, 3, -4, 5]

[1, -2, 3, -4, 5, -3, 2, 2, 2] >>> subarray: [1, -2, 3, -4, 5]

Remember that these are just 5 of the possible contiguous subarrays from i=0 to i=4.

Repeat this pattern for all subsequent values in A. As you can guess, the number of possible contiguous subarrays increases rapidly as A gets longer. This brute force method will not do, as it has O(N²) runtime complexity. Kadane’s Algorithm is O(N).

Keep reading to see how it’s done.

Kadane’s Algorithm

If you’re familiar with derivatives in calculus, you’ll know that they measure rates of change in a given equation. Grant Sanderson of 3Blue1Brown won’t like that phrasing, but it works for our purposes.

Kadane’s Algorithm works like a calculus derivative, in the sense that the rate of change from one value to the next in A is being checked. To put it another way:

Kadane’s Algorithm indirectly finds the maximum sum of all possible contiguous subarrays in an array A by updating a cumulative sum variable based on whether or not the given value at index i in A increases the cumulative sum variable.

Read that again.

Now let’s check out A:

[1, -2, 3, -4, 5, -3, 2, 2, 2]

With a variable max_sum = 0, add A[0] to max_sum because 0 + 1 > 0.

[1, -2, 3, -4, 5, -3, 2, 2, 2]

Here max_sum = 1, so 1 + -2 = -1. No update for max_sum, so max_sum = 1.

[1, -2, 3, -4, 5, -3, 2, 2, 2]

Here max_sum = 1, so 1 + 3 = 4. max_sum gets updated because 1 + 3 > 1, so max_sum = 4.

Notice how we were comparing two values to each other at each index?

You need 2 variables: a local maximum (local_max, for comparing A[i] and A[i] + local_max) and a global maximum (max_sum, the maximum possible sum).

The local maximum compares the cumulative sum value (CVS) to the CVS plus the current value in A. The local max gets updated to whatever value is greater:

local_max = max(local_max, local_max + A[i])

The max_sum value gets updated the value of local_max if local_max is greater.

Repeat this process for each value in A. Here is the code in Python:

def kadane(nums):
    local_sum = 0
    global_sum = nums[0]
    for i in nums:
        local_sum = max(i, i + local_sum)
        global_sum = max(global_sum, local_sum)
    return global_sum

Thanks for reading, and feel free to ask me any questions you have or give me feedback!

- John