Maximum Subarray

The problem

You are given a list of whole numbers, nums. They can be positive, negative or zero. A subarray is one or more numbers that sit next to each other in the list, taken in order. Return the largest sum that any subarray has. A subarray cannot be empty, so when every number is negative, the answer is the largest single number.

What to write

function solve(nums: number[]): number

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

Output
6

Input
nums = [1]

Output
1

Constraints

1–10,000 integers within ±10,000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   With 10,000 numbers there are about 50 million subarrays, one for every choice of a first and a last number, so look for a way to handle each number once. Notice what makes the problem hard: the negative numbers. If there were none, the answer would be the sum of the whole list.

2. Hint 2: Ask a smaller question

   In 5, -9, 4, 7 the best subarray is 4, 7, with sum 11. Why does it not reach back to the 5? Add up what the 5 and the -9 would bring to it. What would have to be true of the numbers before the 4 for them to be worth keeping?

3. Hint 3: Name the pattern

   A subarray that ends right before a number is worth extending only if its sum is above zero. So you can settle each number on the spot: extend the subarray you are carrying, or start again here. Deciding each step from what you know now, and never going back, is called a greedy choice. Read the lesson on greedy choice.

4. Hint 4: State the invariant

   After each number, the current sum is the largest sum of any subarray that ends at that number. The best sum is the largest current sum seen so far. Every subarray ends at some number, so by the end of the list the best sum has covered them all.

5. Hint 5: Sketch the pseudocode

   current = best = the first number. For each later number x, in order: current = the larger of x and current + x. Then best = the larger of best and current. After the last number, return best.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

At each value, choose between starting a new subarray and extending the previous one. Track the best nonempty sum throughout.

The slow way

Try every subarray. For each first number, extend one number at a time, keep a running sum, and remember the largest sum you see. It is correct, and nothing is ever decided early, because every start gets its turn. But n numbers have about n × n / 2 subarrays: about 50 million when there are 10,000 numbers.

The insight

Group the subarrays by where they end. The best one ending at a number is that number alone, or that number added to the best one ending right before it. So one sum is all you carry forward, and each number needs one choice: extend or start again. A method that makes each choice on the spot and never revisits it is called greedy.

Step by step

1. Start the current sum and the best sum at the first number. The current sum is the largest sum of a subarray ending at the number you are on. So far the only subarray is the first number by itself, so both sums are that number.
2. Go through the rest of the numbers from left to right. The first number is already counted. The order matters because the choice at each number uses the current sum of the number right before it.
3. Add this number to the current sum, or start again from this number. A subarray ending here is this number alone, or this number added to one ending right before it. The larger sum is the one worth carrying. Adding loses only when the current sum has dropped below zero.
4. Raise the best sum if the current sum is larger. The best subarray ends at some number, and at that number the current sum equals the best subarray's sum. Checking at every number means that moment cannot slip past.
5. Return the best sum. Every number has had its turn as the last number of a subarray. The largest sum over all those endings is the largest sum of any subarray.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Start the current sum and the best sum at the first number
  let current = nums[0],
    best = current;
  // 2. Go through the rest of the numbers from left to right
  for (let i = 1; i < nums.length; i++) {
    // 3. Add this number to the current sum, or start again from this number
    current = Math.max(nums[i], current + nums[i]);
    // 4. Raise the best sum if the current sum is larger
    best = Math.max(best, current);
  }
  // 5. Return the best sum
  return best;
}

function solve(nums: number[]): number {
  // 1. Start the current sum and the best sum at the first number
  let current = nums[0],
    best = current;
  // 2. Go through the rest of the numbers from left to right
  for (let i = 1; i < nums.length; i++) {
    // 3. Add this number to the current sum, or start again from this number
    current = Math.max(nums[i], current + nums[i]);
    // 4. Raise the best sum if the current sum is larger
    best = Math.max(best, current);
  }
  // 5. Return the best sum
  return best;
}

def solve(nums):
    # 1. Start the current sum and the best sum at the first number
    current = best = nums[0]
    # 2. Go through the rest of the numbers from left to right
    for i in range(1, len(nums)):
        # 3. Add this number to the current sum, or start again from this number
        current = max(nums[i], current + nums[i])
        # 4. Raise the best sum if the current sum is larger
        best = max(best, current)
    # 5. Return the best sum
    return best

Example 1, traced

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

Output
6

Why it works

A greedy choice is safe only if it never needs undoing. Here is why this one never does. A subarray ending at a number is that number alone, or that number added to one ending right before it, and the same number added to a larger sum gives a larger total. So only the largest earlier sum can win: nothing you drop could have beaten what you keep.

Time and space

Time O(n), extra space O(1). The loop makes one pass: it visits each number after the first once and does two comparisons for it, so the time is O(n). Only two numbers are stored, the current sum and the best sum, whatever the length of the list: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not start the best sum at 0. A subarray cannot be empty, so for -3, -1, -2 the answer is -1, but a best sum that starts at 0 is never beaten and 0 is returned.
• Start again when the current sum is negative, not when the number is. In example 1 the best subarray, 4, -1, 2, 1, contains a -1, and cutting the list at every negative number finds 4, not 6.
• Return the best sum, not the current sum. The current sum only covers subarrays that end at the last number. In example 1 the current sum finishes at 5, while the best subarray ended two numbers earlier with 6.

Pattern

Greedy choice. Builds on Best Time to Buy And Sell Stock.

Keep going