Maximum Product Subarray

Medium

The problem

Given a slice of integers, find the contiguous part (at least one element) whose numbers multiply to the largest product, and return that product.

Example 1
Input: nums = [2, 3, -2, 4]
Output: 6
The part [2, 3] gives 6.
Example 2
Input: nums = [-2, 0, -1]
Output: 0
Any part with the 0 gives 0, and the others are negative.
Example 3
Input: nums = [-2, 3, -4]
Output: 24
The whole slice: two negatives multiply to a positive.

Limits

1 ≤ len(nums) ≤ 20,000
-10 ≤ nums[i] ≤ 10
The answer fits in a 32-bit integer

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

A very negative product can become the biggest after one more negative number. What two values must you track?

The idea

Track both the max and min product ending at each index; a negative number swaps them.

Target: O(n) time, O(1) space

Go function shape

func maxProduct(nums []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// MaxProduct: a negative number can flip the smallest product into the largest,
// so track BOTH the max and the min product of a subarray ending here.
func MaxProduct(nums []int) int {
	best, hi, lo := nums[0], nums[0], nums[0]
	for _, n := range nums[1:] {
		a, b := hi*n, lo*n
		hi = max(n, max(a, b))
		lo = min(n, min(a, b))
		best = max(best, hi)
	}
	return best
}

Read the lesson: Dynamic Programming