11  Maximum Subarray

Rank 9 · Pattern: Kadane’s algorithm / compressed dynamic programming · Target: \(O(n)\) time, \(O(1)\) space

11.1 Problem definition

Given an integer array nums, return the greatest sum among all of its nonempty contiguous subarrays.

11.2 Clarifying questions

1. Is the input guaranteed to contain at least one value?
2. Should I return only the maximum sum or also the subarray’s boundaries?
3. Is an empty subarray a valid choice?
4. What numeric range should I use for accumulated sums?

11.3 Sample answers

1. Yes. nums is non-null and nonempty.
2. Return only the sum.
3. No. The chosen subarray must be nonempty, so an all-negative input returns its largest element rather than 0.
4. Assume every relevant sum fits in a signed 32-bit int.

11.4 State and recurrence

Enumerating all start/end pairs costs \(O(n^2)\) even with prefix sums. The key is that only one fact about the previous position matters.

Define endingHere as the maximum sum of a nonempty subarray ending exactly at the current index. At value x, either:

• start a new subarray at x, or
• extend the best subarray ending at the previous index.

So:

\[ endingHere_i = \max(nums_i, endingHere_{i-1} + nums_i) \]

best is the maximum endingHere seen anywhere.

Invariant: after processing index i, endingHere is optimal among subarrays ending at i, and best is optimal among all subarrays contained in 0..i.

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

value	ending here	best
-2	-2	-2
1	1	1
-3	-2	1
4	4	4
-1	3	4
2	5	5
1	6	6
-5	1	6
4	5	6

11.5 Minimal solution

Java

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class MaximumSubarraySolution {
    static int maxSubarray(int[] nums) {
        int endingHere = nums[0];
        int best = nums[0];

        for (int i = 1; i < nums.length; i++) {
            endingHere = Math.max(nums[i], endingHere + nums[i]);
            best = Math.max(best, endingHere);
        }
        return best;
    }

    @Test public void findsBestRange() {
        assertEquals(6, maxSubarray(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }

    @Test public void handlesAllNegativeValues() {
        assertEquals(-2, maxSubarray(new int[] {-8, -2, -5}));
    }

    @Test public void handlesSingleValue() {
        assertEquals(7, maxSubarray(new int[] {7}));
    }

    @Test public void mayUseTheEntireArray() {
        assertEquals(6, maxSubarray(new int[] {1, 2, 3}));
    }

    @Test public void startsNewSubarrayAfterLargeLoss() {
        assertEquals(13, maxSubarray(new int[] {5, -100, 6, 7}));
    }

    @Test public void keepsBestEarlierSubarray() {
        assertEquals(5, maxSubarray(new int[] {5, -6, 4}));
    }

    @Test public void handlesZeros() {
        assertEquals(0, maxSubarray(new int[] {0, -1, 0}));
    }

    public static void main(String[] args) {
        JUnitCore.main("MaximumSubarraySolution");
    }
}

Python

import unittest


def max_subarray(nums):
    ending_here = nums[0]
    best = nums[0]

    for value in nums[1:]:
        ending_here = max(value, ending_here + value)
        best = max(best, ending_here)

    return best


class MaximumSubarrayTests(unittest.TestCase):
    def test_finds_best_range(self):
        self.assertEqual(6, max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

    def test_handles_all_negative_values(self):
        self.assertEqual(-2, max_subarray([-8, -2, -5]))

    def test_handles_single_value(self):
        self.assertEqual(7, max_subarray([7]))

    def test_may_use_entire_array(self):
        self.assertEqual(6, max_subarray([1, 2, 3]))

    def test_starts_new_subarray_after_large_loss(self):
        self.assertEqual(13, max_subarray([5, -100, 6, 7]))

    def test_keeps_best_earlier_subarray(self):
        self.assertEqual(5, max_subarray([5, -6, 4]))

    def test_handles_zeros(self):
        self.assertEqual(0, max_subarray([0, -1, 0]))


if __name__ == "__main__":
    unittest.main()

Rust

pub fn max_subarray(nums: &[i32]) -> i32 {
    let mut ending_here = nums[0];
    let mut best = nums[0];

    for &value in &nums[1..] {
        ending_here = value.max(ending_here + value);
        best = best.max(ending_here);
    }

    best
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn finds_best_range() {
        assert_eq!(6, max_subarray(&[-2, 1, -3, 4, -1, 2, 1, -5, 4]));
    }

    #[test]
    fn handles_all_negative_values() {
        assert_eq!(-2, max_subarray(&[-8, -2, -5]));
    }

    #[test]
    fn handles_single_value() {
        assert_eq!(7, max_subarray(&[7]));
    }

    #[test]
    fn may_use_entire_array() {
        assert_eq!(6, max_subarray(&[1, 2, 3]));
    }

    #[test]
    fn starts_new_subarray_after_large_loss() {
        assert_eq!(13, max_subarray(&[5, -100, 6, 7]));
    }

    #[test]
    fn keeps_best_earlier_subarray() {
        assert_eq!(5, max_subarray(&[5, -6, 4]));
    }
}

Initializing from nums[0] rather than zero is what makes all-negative inputs correct.

11.6 High-value tests

Input	Expected	Purpose
[7]	7	one value
[-8,-2,-5]	-2	all negative
[1,2,3]	6	entire array
[-2,1,-3,4,-1,2,1,-5,4]	6	interior range
[0,-1,0]	0	zeros

11.7 Complexity and correctness

The array is scanned once, giving \(O(n)\) time and \(O(1)\) working space.

Any optimal subarray ending at i either contains the previous position or starts at i; there is no third form. If it contains the previous position, extending the best such prior subarray is never worse than extending another. The recurrence therefore computes the exact local optimum, and best takes the maximum of all possible ending positions.

11.8 If the interviewer pushes

• Return indices by tracking the tentative start whenever a new subarray begins, and save the best boundaries.
• Use long if sums may exceed the int range.
• For a circular array, combine Kadane’s maximum with total sum minus a minimum-subarray result, handling the all-negative case separately.
• A divide-and-conquer solution is \(O(n\log n)\) and demonstrates a different pattern but is not an improvement here.

11.9 TDD interview script

Confirm that input is non-null and nonempty, the chosen subarray must be nonempty and contiguous, only the sum is returned, and relevant sums fit in int. Then write this test list:

1. One value
2. All positive values
3. Forced restart
4. Earlier best that must be retained
5. All negative values
6. Zeros
7. Standard mixed example

Add one focused test per red–green–refactor cycle. Verify the failure, introduce the smallest recurrence or state change, rerun the complete example, and refactor only while green. Tests assert the result, not the internal dynamic-programming variables.

From book/src, run:

Java

./java/run.sh MaximumSubarraySolution

Python

./python/run.sh maximum_subarray_solution

Rust

./rust/run.sh maximum_subarray_solution

Explain the two pieces of state before generalizing: endingHere answers a constrained question about subarrays ending at the current index, while best remembers the unconstrained maximum over every ending position seen so far.

11.9.1 Pseudocode

endingHere = nums[0]
best = nums[0]

for each x after nums[0]:
    endingHere = max(x, endingHere + x)
    best = max(best, endingHere)

return best

The invariant is: after index i, endingHere is the greatest sum of a nonempty subarray ending exactly at i, and best is the greatest sum of any subarray within 0..i.

11.9.2 TDD sequence

Step	Test code added	Production code added or changed
1. Required element	handlesSingleValue	Initialize both state variables from nums[0], preserving the nonempty-subarray contract.
2. Extend a winner	mayUseTheEntireArray	Iterate from index one and extend the previous ending sum when doing so is beneficial.
3. Restart after loss	startsNewSubarrayAfterLargeLoss	Set endingHere to max(x, endingHere + x) so a new subarray can begin at the current value.
4. Preserve global best	keepsBestEarlierSubarray	Track best separately from endingHere; a later local result must not erase an earlier maximum.
5. No empty escape	handlesAllNegativeValues	Triangulate initialization from the first element rather than zero, so the least-negative value wins.
6. Zero boundary	handlesZeros	Verify that zero can be the optimal nonempty sum without special-case logic.
7. Mixed acceptance case	findsBestRange	Exercise several extensions, restarts, and best updates in one standard example.

The sequence derives Kadane’s recurrence from two choices at each position—start or extend—and uses focused regressions to keep the local and global optima distinct.