Maximum Product Subarray

Problem

Given an integer array nums, find a contiguous, non-empty subarray whose elements multiply to the largest possible value, and return that product. The product of any prefix or subarray is guaranteed to fit in a 32-bit signed integer.

• nums holds up to about twenty thousand integers.
• Each value is small (say, between -10 and 10), and every intermediate product fits comfortably in a normal signed integer.

Examples

• nums = [3, 4, -3, 5] → 12, from the subarray [3, 4]. Including the -3 flips the sign.
• nums = [-5, 0, -2] → 0. Any subarray containing both negatives also contains the zero.
• nums = [-3, 5, -2] → 30. Two negatives multiply to a positive, so the whole array is best.

Hints

1. Try the maximum-sum-subarray (Kadane) idea, keeping the best product ending at each index. Where does it fail?
2. A very negative running product is one negative number away from becoming very positive. What second quantity should you track?
3. Keep both the maximum and minimum product ending at the current index; a negative element swaps their roles.