Maximum Product Subarray

The problem

Given a list of whole numbers nums with at least one number in it, return the largest product of a subarray. A subarray is a run of one or more numbers that sit next to each other in the list, and its product is what you get by multiplying them all. The numbers can be negative or zero. A single number is a run too, and its product is the number itself.

What to write

function solve(nums: number[]): number

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

Output
6

Input
nums = [-2,0,-1]

Output
0

Constraints

Values may be negative or zero; intermediate products fit a signed 32-bit integer.

Hints

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

1. Hint 1: Use the constraints

   The numbers can be negative or zero. One negative number turns a large product into a very small one, and a second negative number turns it back. A zero wipes out every product that runs through it. So the largest product so far is not the whole story.

2. Hint 2: Ask a smaller question

   Take -2, 3, -4. Standing at the 3, the largest product of a run that ends there is 3. Then -4 arrives and the answer becomes 24. Which product ending at the 3 did the 24 grow from?

3. Hint 3: Name the pattern

   The best run ending at a number is built from the runs ending at the number before it. Carrying an answer forward from each position to the next is one-dimensional dynamic programming. Here two answers are carried, the largest product and the smallest, because a negative number swaps them. The signal: you want the best run of neighbors. Read the lesson on one-dimensional dynamic programming.

4. Hint 4: State the invariant

   At each number keep two values: the largest product of any run that ends exactly at this number, and the smallest. Each comes from three candidates: the number alone, the number times the old largest, and the number times the old smallest. A third value, the best, is the largest product seen at any position so far.

5. Hint 5: Sketch the pseudocode

   largest = smallest = best = the first number. For each later number x: work out x, x × largest and x × smallest. The new largest is the biggest of those three and the new smallest is the least of them. Then best = the bigger of best and largest. Return best.

Solution

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

Approach

Track both maximum and minimum products ending here, since multiplying by a negative number exchanges their roles.

The slow way

Work out the product of every run: for each start, extend to each end, multiplying in one more number each time, and keep the largest product seen. It is correct, but a list of n numbers has about n × n / 2 runs: 10 runs for 4 numbers and 5,050 for 100.

The insight

A run that ends at a number is that number alone, or a run that ends one place earlier with the number multiplied in. Of those earlier runs only two matter: the one with the largest product and the one with the smallest, because multiplying by a negative number turns the smallest into the largest.

Step by step

1. Start with the first number as the largest, smallest and best product. Only one run ends at the first number: the number alone. So it is the largest and the smallest product ending there, and the best product seen so far.
2. Try each later number alone, times the largest and times the smallest. A run that ends here either starts here or extends a run that ended one place earlier. Of those earlier runs, only the largest product and the smallest product can lead to a new largest or smallest.
3. Keep the largest and the smallest of those three for the next number. The smallest is kept because a later negative number turns it into a large product. Both are picked from the same three candidates, so the old pair is still intact while they are worked out.
4. Raise the best product if the new largest beats it. The best run does not have to reach the end of the list, so the largest product ending at each position is compared with the best seen so far.
5. Return the best product. Every run ends at some position, and the best was compared with the largest product ending at each one, so no run was missed.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Start with the first number as the largest, smallest and best product
  let high = nums[0],
    low = nums[0],
    best = nums[0];
  // 2. Try each later number alone, times the largest and times the smallest
  for (let i = 1; i < nums.length; i++) {
    const n = nums[i],
      a = high * n,
      b = low * n;
    // 3. Keep the largest and the smallest of those three for the next number
    high = Math.max(n, a, b);
    low = Math.min(n, a, b);
    // 4. Raise the best product if the new largest beats it
    best = Math.max(best, high);
  }
  // 5. Return the best product
  return best;
}

function solve(nums: number[]): number {
  // 1. Start with the first number as the largest, smallest and best product
  let high = nums[0],
    low = nums[0],
    best = nums[0];
  // 2. Try each later number alone, times the largest and times the smallest
  for (let i = 1; i < nums.length; i++) {
    const n = nums[i],
      a = high * n,
      b = low * n;
    // 3. Keep the largest and the smallest of those three for the next number
    high = Math.max(n, a, b);
    low = Math.min(n, a, b);
    // 4. Raise the best product if the new largest beats it
    best = Math.max(best, high);
  }
  // 5. Return the best product
  return best;
}

def solve(nums):
    # 1. Start with the first number as the largest, smallest and best product
    high = low = best = nums[0]
    # 2. Try each later number alone, times the largest and times the smallest
    for i in range(1, len(nums)):
        num = nums[i]
        candidates = (num, high * num, low * num)
        # 3. Keep the largest and the smallest of those three for the next number
        high, low = max(candidates), min(candidates)
        # 4. Raise the best product if the new largest beats it
        best = max(best, high)
    # 5. Return the best product
    return best

Example 1, traced

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

Output
6

Why it works

After each number, one value is the largest product of any run that ends exactly there, and another is the smallest. A run ending at the next number is that number alone or an earlier run times the number. Multiplying products by the same number keeps their order or reverses it, so the new largest and smallest come from the old largest and smallest, or from the number alone.

Time and space

Time O(n), extra space O(1). One pass over the n numbers, with a fixed amount of work for each, gives O(n) time. Only three values are kept, whatever the length of the list, so the space is O(1).

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

• Keeping only the largest product. In -2, 3, -4 the largest product ending at 3 is 3, and 3 × -4 is -12, so that version answers 3. The 24 comes from the smallest, -6, times -4.
• Replacing the largest and then using the new value to work out the smallest. Both must come from the old pair. For 3, -3, -3, -3 the mixed-up version returns 243 instead of 27.
• Starting the best at 0. A list that holds only -2 has the answer -2, and that version returns 0. Start the best at the first number.

Pattern

One-dimensional dynamic programming. Builds on House Robber.

Keep going