Sweaty Imposter

Maximum Product Subarray

MediumDynamic Programming (1-D & 2-D)Blind 75MidOpen on LeetCodeUpdated

You're given an integer array nums. Find the contiguous, non-empty subarray whose elements have the largest product, and return that product. The array can contain negative numbers and zeros, and the answer is guaranteed to fit in a 32-bit integer.

Examples

nums = [3,-1,4,2] returns 8

The subarray [4,2] has product 8. Stretching it left to include -1 flips the sign, and the whole array multiplies to -24.

nums = [-2,5,-3] returns 30

The two negatives cancel, so the whole array gives -2 * 5 * -3 = 30, which beats 5 on its own.

nums = [-1,0,-5] returns 0

Every subarray that avoids the 0 is a single negative number, so the best product is the 0 itself.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -10 <= nums[i] <= 10
  • The product of any subarray of nums fits in a 32-bit integer.

Hints

Hint 1

In Maximum Subarray you only kept the best sum ending at each index. Why is the best product ending at i not enough here?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Kadane's idea, extended for signs. A negative number turns the smallest product ending at the previous index into the largest one, so track both the maximum and the minimum product of a subarray ending at i. At each element, swap the two if the element is negative, then set hi = max(x, hi * x) and lo = min(x, lo * x), and fold hi into the running best. Taking x on its own restarts the subarray, which also handles zeros. One pass, O(n) time and O(1) space.

Time

O(n)

Space

O(1)

Pitfall

Tracking only the maximum product, as in Maximum Subarray. A large negative product is one negative number away from being the answer, so dropping the minimum loses cases like [-2,5,-3].

Solutions

class Solution {
    public int maxProduct(int[] nums) {
        int best = nums[0], hi = nums[0], lo = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            if (x < 0) {
                int t = hi;
                hi = lo;
                lo = t;
            }
            hi = Math.max(x, hi * x);
            lo = Math.min(x, lo * x);
            best = Math.max(best, hi);
        }
        return best;
    }
}
Drill This