Maximum Subarray

Given an integer array nums, find the contiguous non-empty subarray with the largest sum and return that sum. This is LeetCode 53. The limits are 1 <= nums.length <= 10^5 and -10^4 <= nums[i] <= 10^4.

The page gives two solutions. Solution 1 tries every start index and is easy to trust but takes O(n^2) time. Solution 2 is Kadane's algorithm, which makes one pass in O(n) time and O(1) space.

Example 1
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: the subarray [4, -1, 2, 1] has the largest sum.
Example 2
Input: nums = [1]
Output: 1
Example 3
Input: nums = [5, 4, -1, 7, 8]
Output: 23
Explanation: the whole array is the best subarray.

How to Think About It

Step 1: Check every subarray

A subarray is fixed by its first index i and its last index j. There are about n^2 / 2 such pairs. Summing each pair from scratch costs O(n) more, which gives O(n^3).

Step 2: Reuse the running sum

For a fixed start i, the sum of nums[i..j+1] is the sum of nums[i..j] plus nums[j+1]. So one inner loop that keeps adding gives every subarray starting at i. That is O(n^2), and it is Solution 1.

Step 3: Ask a smaller question at each index

Instead of asking about every pair, ask: what is the best sum of a subarray that ends exactly at index i? Call it current. Such a subarray either is nums[i] alone, or it extends the best subarray ending at i - 1. So:

current = max(nums[i], current + nums[i])

Why is extending the best one enough? Any subarray ending at i that includes i - 1 has the form (something ending at i - 1) plus nums[i]. The largest such sum uses the largest "something", which is the old current.

Step 4: A negative prefix is dead weight

Read the formula in words: if the running sum before i is negative, it only drags nums[i] down, so start fresh at i. Otherwise keep extending. The answer is the largest current seen at any index, because the best subarray must end somewhere.

This is a one-variable dynamic programming recurrence, known as Kadane's algorithm. The introduction to dynamic programming explains the general idea of building an answer from the answer one step back.

Walkthrough

Solution 2 on Example 1, nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Both variables start at nums[0] = -2.

inums[i]Choicecurrentbest
0-2first element-2-2
11start fresh, -2 + 1 is worse than 111
2-3extend-21
34start fresh, -2 + 4 is worse than 444
4-1extend34
52extend55
61extend66
7-5extend16
84extend56

The best value, 6, was reached at index 6. The run that produced it started at index 3, which is the subarray [4, -1, 2, 1].

Solution 1: Brute Force

This method fixes each start index in turn and extends the subarray one element at a time, keeping a running sum.

  • The running sum: sum is reset to 0 for each new start i, then grows by nums[j], so it always equals the sum of nums[i..j].
  • Checking after every add: best is compared after each step of the inner loop, so every subarray, including single elements, is considered.
  • Starting value of best: Integer.MIN_VALUE is lower than any real sum, so the first subarray always replaces it.
  • Large inputs: at n = 10^5 the inner statement runs about 5 × 10^9 times. A test run on 10^5 elements took about 3 seconds, which is too slow for LeetCode's largest tests.

A common mistake is to start with best = 0, thinking an empty subarray is allowed. The problem asks for a non-empty subarray, so [-3, -1, -2] must return -1, but that version returns 0.

Java
public class MaximumSubarrayBruteForce {

    public int maxSubArray(int[] nums) {
        int best = Integer.MIN_VALUE;      // lower than any real sum
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;                   // sum of nums[i..j]
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                best = Math.max(best, sum);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        MaximumSubarrayBruteForce solver = new MaximumSubarrayBruteForce();
        System.out.println(solver.maxSubArray(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}));  // 6
        System.out.println(solver.maxSubArray(new int[] {5, 4, -1, 7, 8}));                 // 23
    }
}

Solution 2: Kadane's Algorithm

Kadane's algorithm walks the array once and keeps the best sum of a subarray that ends at the current index, plus the best sum seen anywhere.

  • Seeding with the first element: current and best both start at nums[0], and the loop starts at index 1. A one-element array such as Example 2 returns that element.
  • Extend or restart: Math.max(nums[i], current + nums[i]) restarts exactly when the old current is negative, because only then is adding it worse than leaving it out.
  • All negative numbers: every step restarts, so current is just nums[i] and best becomes the largest element. [-3, -1, -2] returns -1.
  • No overflow: the largest possible sum is 10^5 × 10^4 = 10^9, which fits in an int.

A common mistake is to start current at 0 while still looping from index 1. Then nums[0] never joins a running sum, and Example 3 returns 18 (4 - 1 + 7 + 8) instead of 23.

Java
public class MaximumSubarray {

    public int maxSubArray(int[] nums) {
        int current = nums[0];     // best sum of a subarray ending at index i
        int best = nums[0];        // best sum seen anywhere so far
        for (int i = 1; i < nums.length; i++) {
            current = Math.max(nums[i], current + nums[i]);  // restart if the old run is negative
            best = Math.max(best, current);
        }
        return best;
    }

    public static void main(String[] args) {
        MaximumSubarray solver = new MaximumSubarray();
        System.out.println(solver.maxSubArray(new int[] {-2, 1, -3, 4, -1, 2, 1, -5, 4}));  // 6
        System.out.println(solver.maxSubArray(new int[] {1}));                              // 1
        System.out.println(solver.maxSubArray(new int[] {5, 4, -1, 7, 8}));                 // 23
    }
}

Complexity

  • Solution 1 time: O(n^2). For each of the n start indices the inner loop runs to the end of the array, so it does n + (n - 1) + ... + 1 = n(n + 1) / 2 constant-time steps.
  • Solution 1 space: O(1). Only the two loop indices, the running sum and best are stored, and none of them depend on the array length.
  • Solution 2 time: O(n). The single loop visits each index from 1 to n - 1 once and does two Math.max calls per visit, with no inner loop.
  • Solution 2 space: O(1). The recurrence only needs the answer for index i - 1, so one variable current replaces a whole dp array.

Which One to Use

Use Kadane's algorithm in practice and in interviews: it is just as short, runs in linear time, and passes the 10^5 limit easily. The brute force is still worth writing once, because it is obviously correct and makes a good reference to test Kadane's algorithm against. Both always return the same sum, since each considers every subarray, one directly and one through the recurrence. The brute force has one advantage: it visits every subarray explicitly, which helps when a problem asks about all subarrays rather than just the best one.

The same idea with a wrap-around twist is Maximum Sum Circular Subarray, and with products instead of sums it becomes Maximum Product Subarray.