Maximum Subarray

The problem

You are given an array nums of whole numbers (call its length n). A subarray is a run of one or more numbers that sit next to each other. Find the subarray with the largest sum, and return that sum.

Example 1

Input: nums = [3, -5, 4, -1, 2, 1, -6, 2]

Output: 6

4 − 1 + 2 + 1 = 6. Adding the 3 and −5 in front would lower it, and so would the −6 after it.

nums

30-5142-132415-6627

Example 2

Input: nums = [-3, -1, -2]

Output: -1

Every number is negative. The best subarray is the single largest number.

Example 3

Input: nums = [5, -2, 7]

Output: 10

The −2 is worth crossing to reach the 7: 5 − 2 + 7 = 10.

Constraints

• 1 ≤ n ≤ 100,000
• −10,000 ≤ nums[i] ≤ 10,000

Clarifying questions

Can the subarray be empty?

No. It has at least one number, so with all negatives the answer is negative.

Do we return the sum or the subarray?

Only the sum.

Must the numbers be next to each other?

Yes. That is what makes it a subarray and not a subset.

Can the sum overflow?

No. At most 100,000 × 10,000 = 1,000,000,000, which fits in 32 bits.

Spot the pattern

The best subarray that ends at index i either is nums[i] alone, or extends the best subarray that ends at i − 1. So each answer is built from the one just before it. That is dynamic programming with a single number of state, known as Kadane’s algorithm.

Solutions

Every startO(n²)Kadane's algorithmO(n)

Show all

Adding up every subarray from scratch is O(n³), just a slower brute force. A divide and conquer answer runs in O(n log n), still slower than Kadane.

Every start O(n²)

The idea

Try every start i. From there, move j to the right and keep a running total, so each longer subarray costs one more addition. Keep the largest total ever seen.

It checks every subarray, so it cannot miss the best one. But there are about n² / 2 of them.

Walkthrough

nums

30-5142-132415-6627

best

3

1. best = nums[0]
2. for i in range(len(nums)):
3. total = 0
4. for j in range(i, len(nums)):
5. total += nums[j]
6. best = max(best, total)
7. return best

Try every start i. From each start, extend j to the right and keep a running total, so each new subarray costs one addition.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Every start: from each start, extend to the right with a running total.
    // About n * n / 2 subarrays, so O(n^2) time and O(1) memory.
    public int maxSubArray(int[] nums) {
        int best = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int total = 0;
            // Each longer subarray is the last one plus one number: one addition.
            for (int j = i; j < nums.length; j++) {
                total += nums[j];
                best = Math.max(best, total);
            }
        }
        return best;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines add one number and compare. They sit inside two loops. That small job does not grow with n, so each run is 1 step.

   1. best = nums[0]
   2. for i in range(len(nums)):
   3. total = 0
   4. for j in range(i, len(nums)):
   5. total += nums[j]
   6. best = max(best, total)
   7. return best

2. 2 Count the runs on Example 1

   Example 1 has 8 numbers. Start 0 has 8 subarrays, start 1 has 7, and so on down to start 7, which has 1.

   8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 runs.

   start i	0	1	2	3	4	5	6	7
   inner runs	8	7	6	5	4	3	2	1

   total

   8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36

3. 3 Write the count for any n

   n + (n − 1) + … + 1 = n × (n + 1) / 2 = ½n² + ½n

   Check it with Example 1: 8 × 9 / 2 = 36.

4. 4 Keep only the part that grows fastest

   • Drop the +½n. Next to ½n² it soon stops mattering.
   • Drop the ½. It does not change how fast the count grows.

   What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code keeps best, i, j and total. That is fixed, for any n, so the space is O(1).

   bestijtotal

Kadane's algorithm O(n)

The idea

Walk the array once. Keep best_ending_here: the best sum of a subarray that ends at the current number.

For each new number there are only two choices. Extend the run that ended just before, giving best_ending_here + number, or start a new run at number. Take the bigger one: best_ending_here = max(number, best_ending_here + number). In plain words: if the run so far has gone negative, it can only drag number down, so drop it.

Every subarray ends somewhere, so the answer is the largest best_ending_here ever seen. Keep it in best.

Why it never misses the answer: the best subarray ends at some index. At that index, best_ending_here is at least its sum, because best_ending_here is the best of all subarrays ending there.

Walkthrough

nums

30-5142-132415-6627

i

best_ending_here

3

best

3

1. best_ending_here = best = nums[0]
2. for number in nums[1:]:
3. best_ending_here = max(number, best_ending_here + number)
4. best = max(best, best_ending_here)
5. return best

best_ending_here is the best sum of a subarray that ends here. At index 0 that is just 3. best is the largest best_ending_here seen.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Kadane's algorithm: bestEndingHere is the best sum of a subarray ending here.
    // Extend it or start fresh, whichever is bigger. O(n) time, O(1) memory.
    public int maxSubArray(int[] nums) {
        // Not 0: the subarray cannot be empty, so all negatives must give a negative.
        int bestEndingHere = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int number = nums[i];
            // A negative run so far only drags number down, so then start again at number.
            bestEndingHere = Math.max(number, bestEndingHere + number);
            best = Math.max(best, bestEndingHere);
        }
        return best;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop does one addition and two max calls. That is 1 step. There is one loop.

   1. best_ending_here = best = nums[0]
   2. for number in nums[1:]:
   3. best_ending_here = max(number, best_ending_here + number)
   4. best = max(best, best_ending_here)
   5. return best

2. 2 Count the runs on Example 1

   Example 1 has 8 numbers. The first one sets best_ending_here, and the loop handles the other 7.

   7 runs.

   	run 1	run 2	run 3	run 4	run 5	run 6	run 7
   number	-5	4	-1	2	1	-6	2
   best_ending_here	-2	4	3	5	6	0	2

3. 3 Write the count for any n

   n − 1 runs

   Check it with Example 1: 8 − 1 = 7.

4. 4 Keep only the part that grows fastest

   Drop the − 1. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps two numbers, best_ending_here and best. The space is O(1).

   best_ending_herebest

Common mistake

Starting best at 0

With best = 0, an array of only negative numbers returns 0. But the subarray cannot be empty, so the answer must be one of the numbers. Start best_ending_here and best at nums[0].

Tested at the limits

2,000 random arrays of 1 to 10 numbers from −5 to 5, and about one in five all negative. Every start and Kadane's algorithm gave the same answer every time.

Largest inputs	Result
100,000 numbers (the most allowed), from −10,000 to 10,000. Kadane algorithm. Also run with every number negative.	0.01 s, and under 0.001 MB of extra memory: just two numbers.
2,000 numbers. Every start, about 2 million sums.	0.1 s. At 100,000 numbers it would add 5 billion sums, which is why Kadane matters.