Code Logo

Maximum Product Subarray

Published atDate not available
Created by
Hard 0 views
Like0

This problem asks for the biggest product you can make from one continuous part of the list. A product means you multiply the numbers together, not add them. The chosen numbers must stay next to each other, because you are looking for a subarray.

This puzzle gets interesting because negative numbers can completely change the result. A negative number can make the product smaller, but two negatives together can suddenly turn the product positive again. Zero can also break a streak, because multiplying by zero resets everything to zero.

For example, in [2,3,-2,4], the best answer is 6 from the subarray [2,3]. If you keep going and include -2, the product changes in a bad way. But in [-2,3,-4], the full subarray gives 24, because -2 × 3 × -4 = 24. In [-2,0,-1], the best answer is 0, since the zero beats the other possible products.

The answer is only the largest product value. You do not need to return the subarray itself, just the best number you can get.

Example Input & Output

Example 1
Input
nums = [2,3,-2,4]
Output
6
Explanation

Example with input: nums = [2,3,-2,4]

Example 2
Input
nums = [-2,3,-4]
Output
24
Explanation

Example with input: nums = [-2,3,-4]

Example 3
Input
nums = [-2,0,-1]
Output
0
Explanation

Example with input: nums = [-2,0,-1]

Algorithm Flow

Recommendation Algorithm Flow for Maximum Product Subarray
Recommendation Algorithm Flow for Maximum Product Subarray

Best Answers

java
class Solution {
    public int max_product(int[] nums) {
        if (nums.length == 0) return 0;
        int res = nums[0], maxP = nums[0], minP = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            if (x < 0) {
                int tmp = maxP; maxP = minP; minP = tmp;
            }
            maxP = Math.max(x, maxP * x);
            minP = Math.min(x, minP * x);
            res = Math.max(res, maxP);
        }
        return res;
    }
}