Kadane’s Algorithm Explained

4 min readApr 6, 2023

Kadane’s Algorithm (a.k.a. maximum sum subarray problem) is a greedy dynamic programming algorithm that calculates the maximum subarray at a particular position. It also helps reduce the time complexity to linear time O(n).

Overview

Kadane’s Algorithm is an iterative greedy dynamic programming algorithm. It is used to calculate the maximum sum contiguous sub-array at a particular position. The maximum subarray problem is the task of finding the largest possible sum of a contiguous sub-array, within a given one-dimensional array of numbers. This algorithm has a time complexity of O(n).

I think that the best way to understand a concept is by solving a problem, so today we will first go over the brute force method, then attempt Kadane’s algorithm.

Let’s run through an example

Let’s go over the problem Maximum Subarray from LeetCode.

We are given an integer array numsand are asked to find the sub-array that is the largest possible sum, and return that value. We will use the first example. See the array below.

We need to keep track of several things:

cur_sum denotes the current sum we have in the given sub-array, we do not want this value to be negative
max_sum denotes the maximum sum of the sub-array, initialize this value at the first position in the array nums[0]
cur_sum size of the input array

Brute Force Method

The naive approach is to:

1. Find all possible contiguous sub-arrays

2. Calculate & keep track of the sum of every possible contiguous sub-array (see the figures below)

3. Find the maximum sub-array value given all of the sums

The brute force method calculates all of the sub arrays starting with index zero, e.g. nums[0], and calculates their respective sums. However, by doing this approach, we would then need to calculate every possible sub-array starting with nums[0], nums[1]` and so on until we reach the length of nums (i.e. the last index of nums).

Q: How would we code it up?

Essentially, we would need two loops: an outer loop to keep track of which iteration we are on and an inner loop to do all of the work.

def kadaneBruteForce(nums):
  max_sum = nums[0]
  for i in range(len(nums)):
    cur_sum = 0
    for j in range(i, len(nums)):
      cur_sum += nums[j]
      max_sum = max(cur_sum, max_sum)
  return max_sum

Are you starting to notice how expensive this could get given a large array? Using the brute force approach, we get time complexity of O(n²). This method would work, but there is duplication and a lot of unnecessary work. We can improve our approach.

Kadane’s Algorithm

Kadane’s Algorithm is a way of calculating the maximum sum of a contiguous sub-array using linear time.

Pseudocode

Here are the steps to implement Kadane’s Algorithm:

Initialize two variables cur_sumand max_sum equal to the first index of the array nums[0]
Iteratively traverse through the array starting at index one, nums[1]

Then for each iteration:

Add the current element to cur_sum
If the current sum becomes negative, reset it to the current index (we don’t want negative numbers since that will bring down our maximum sum)
If the max_sum is greater than cur_sum, update the max_sum
Return the max_sum

Recall that we want to have the maximum contiguous sub-array. Negative values are not desirable, but not necessary to remove each time.

Code Implementation

def maxSubArray(self, nums):
  cur_sum = max_sum = nums[0]
    for n in nums[1:]:
      cur_sum = max(n, cur_sum + n)
      max_sum = max(cur_sum, max_sum)
  return max_sum

With Kadane’s Algorithm we now have linear time, O(n) and reduce the code duplication of a nested loop.

How do I recognize the pattern?

You can ask yourself a few questions:

1. Is the problem statement asking me to use a greedy algorithm?

2. Am I trying to find the maximum contiguous subarray?

Keywords to look out for:

Contiguous increasing array
Contiguous subarray
Maximum (or largest) subarray
Subsequence Sum

This algorithm is very similar to the Sliding Window technique (let’s try that algorithm together in another post).

Recap

Kadane’s Algorithm is a greedy dynamic programming algorithm that calculates the maximum subarray at a particular position. It helps reduce the time complexity to linear time O(n).