Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 225 ยท Arrays and Lists

Subarray Problems and Kadane's Algorithm

Solve the maximum subarray and maximum product subarray problems in Python. Go from a brute force to Kadane's O(n) algorithm, and track the indices too.

A subarray is a block of neighbouring elements: a slice nums[i:j] with no gaps. It is not the same as a subsequence (elements in order, gaps allowed) or a subset (any elements at all). Subarray questions are everywhere in interviews because an array of length n has about nยฒ/2 subarrays, so a naive solution is slow and a clever one has something to show.

The most famous one is the maximum subarray problem: given a list of integers, which contiguous block has the largest sum? The classic linear-time answer is Kadane's algorithm. It is only a few lines long, but it teaches a way of thinking you will reuse in dynamic programming: decide what you know about the best answer ending here, and extend it one step at a time.

If prefix sums are fresh in your mind, Prefix Sums and Difference Arrays is a good companion: it solves range-sum questions with the same "subtract what you do not want" idea.

The problem

TEXT
nums = [2, -3, 4, -1, 2, 1, -5, 4]

 2 -3 [ 4 -1  2  1 ] -5  4
        \_________/
        best block: sum = 6

The answer is 6, from the block [4, -1, 2, 1]. Negative numbers are what make it interesting: if every number were positive you would simply take the whole array. A negative number in the middle is worth keeping only if the positives after it make up for it.

Decide up front what the answer is for an all-negative array such as [-3, -1, -2]. Most versions of the problem require a non-empty subarray, so the answer is -1, not 0. This lesson uses the non-empty rule.

Brute force: try every subarray

The direct idea: for every start i and every end j, add up the block and keep the largest sum. Writing the inner sum as a fresh loop costs O(n) each time and gives O(nยณ) overall. Keeping a running sum while j grows removes the innermost loop and gives O(nยฒ).

Python Brute force: O(n^3) and O(n^2)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For n = 100,000 the quadratic version already needs about five billion additions. We can do much better.

The key idea: the best block that ends here

Let ending_here[i] be the largest sum of a subarray that ends exactly at index i. There are only two choices for such a block:

  1. It is just nums[i] on its own (start fresh here).
  2. It is the best block ending at i - 1, extended by nums[i].

So ending_here[i] = max(nums[i], ending_here[i-1] + nums[i]). Put differently: if the best block ending just before i has a negative sum, it can only hurt you, so drop it and restart at i.

The overall answer is the maximum of ending_here[i] over all i, because the best subarray has to end somewhere. Since each value depends only on the previous one, two variables are enough.

Kadane's algorithm

Python Kadane's algorithm with a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the trace row by row. At x = -3 the running sum drops to -1, which is worse than starting fresh at 4, so at index 2 the algorithm restarts. After that the running sum climbs 4, 3, 5, 6, and then slides down for the -5 without ever beating 6.

TEXT
index:        0   1   2   3   4   5   6   7
nums:         2  -3   4  -1   2   1  -5   4
ending_here:  2  -1   4   3   5   6   1   5
best:         2   2   4   4   5   6   6   6

Complexity

Time Space
Brute force (running sum) O(nยฒ) O(1)
Kadane O(n) O(1)

One pass, a constant number of variables. It also works on a stream: you can feed numbers one at a time without storing them.

Returning the subarray, not only the sum

Interviewers often ask which block it is. Remember where the current block started: whenever you restart (because x alone beats the extended sum), set start = i. Whenever ending_here beats best, record best_start = start and best_end = i.

Python Kadane with indices

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the strict > when updating best: with ties, the first best block is kept. Use >= if you want the last one. Pick a rule and be consistent, especially when a problem says "return the leftmost" or "the shortest".

A prefix-sum view

There is a second way to see the same algorithm. Let prefix[k] be the sum of the first k numbers. The sum of the block from i to j is prefix[j+1] - prefix[i]. To make that large for a fixed j, you want the smallest earlier prefix. So scan once, keep the smallest prefix seen so far, and at each step compare prefix - smallest_prefix_so_far.

Python Maximum subarray as prefix minus smallest prefix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Careful with the order here: the block must be non-empty, so you compare before adding the current prefix to smallest_before. Swap those two lines and an all-negative array would wrongly return 0.

Maximum product subarray

Change the question: which block has the largest product? Kadane's single variable no longer works, because a very negative running product can become a very positive one when multiplied by another negative number. So track two values per position: the largest and smallest product of a block ending here. A negative x swaps their roles.

TEXT
nums = [2, 3, -2, 4]          -> 6    (the block [2, 3])
nums = [-2, 3, -4]            -> 24   (the whole array: two negatives)
nums = [-2, 0, -1]            -> 0    (a zero resets every product)
Python Maximum product subarray

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Comparing a clever solution against a slow, obviously correct one on many inputs is the best way to trust it. We do that on a small scale above; How to Solve Algorithm Problems shows how to do it more systematically.

Maximum circular subarray

Now let the array be circular: a subarray may wrap from the end back to the start, as in [5, -3, 5] where 5 + 5 (indexes 2 and 0) beats any normal block. A wrapping best block means the middle part that is left out is a normal subarray with the smallest sum. So:

TEXT
best circular = total sum - minimum subarray sum
answer        = max(best normal, best circular)

The minimum subarray sum is Kadane's algorithm with min instead of max. One trap: if every number is negative, the "minimum subarray" is the whole array, the circular formula gives 0 (an empty block), and the right answer is just the best normal value, the largest single element.

Python Maximum circular subarray sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Other subarray questions with the same shape

Once you see "best block ending here", many problems fall into place:

  • Circular maximum subarray: the best block may wrap around the end. Answer = max(Kadane on the array, total sum minus the minimum subarray). Be careful when every number is negative: then the second option would select an empty block, so fall back to plain Kadane.
  • Longest subarray with a property: track the length of the current valid block instead of its sum.
  • Subarray sum equals k: needs a dictionary of prefix sums, covered in Prefix Sums and Difference Arrays.
  • Fixed-size windows: use a sliding window.
Python Circular maximum subarray

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Starting best at 0. That silently allows an empty subarray and breaks all-negative inputs. Start from nums[0] (or float("-inf")).
  • Resetting to 0 instead of to x. The classic shortcut cur = max(0, cur + x) is fine only when an empty block is allowed.
  • Forgetting the empty list. Decide whether to raise an error or return 0 before indexing nums[0].
  • Using Kadane for products without tracking the minimum. One variable is not enough once negatives multiply.
  • Mixing up subarray and subsequence. A subsequence is far easier (just add all positives); a subarray must be contiguous.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In Kadane's algorithm, what does the variable ending_here store at index i?

    ending_here is the best block that must finish at i. The overall best is the maximum of these values over all i.
  2. 2. What is the time complexity of the running-sum brute force for maximum subarray?

    There are about n^2/2 start and end pairs, and the running sum makes each one O(1). Re-adding each block from scratch would give O(n^3).
  3. 3. For [-3, -1, -2], what should a non-empty maximum subarray return?

    The block must contain at least one element, so the best choice is the single element -1.
  4. 4. Why does the maximum product subarray need to track a smallest product as well?

    A negative number flips the order: the smallest product so far can become the largest after multiplying by a negative x.
  5. 5. What is the space complexity of Kadane's algorithm?

    It keeps only a few variables (ending_here and best), no matter how long the input is.

Summary

  • A subarray is contiguous; subsequences and subsets are different things.
  • Brute force over all start and end positions is O(nยฒ) with a running sum, O(nยณ) without.
  • Kadane's algorithm computes the best block ending at each index: cur = max(x, cur + x), then best = max(best, cur). It runs in O(n) time and O(1) space.
  • Track the start index when you restart to return the actual block.
  • Maximum product needs both a running maximum and a running minimum.
  • Decide how to treat empty subarrays and all-negative arrays before you code.

Next: Partitioning, Dutch Flag and In-place Tricks, where you will rearrange arrays in place with a couple of pointers.