[LeetCode] 152. Maximum Product Subarray

Posted on | In

Problem

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

1
2
3
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

1
2
3
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Explanation

  1. We can solve this problem in one loop. In each iteration, we need to keep track of the maximum result ending here curMax, and minimum result ending here curMin. We can initialize curMax, curMin, and result res all be the first number of the array.

  2. Start from the second number, let say when we are on the ith number, if the ith number is positive, then we use the current maximum number multiple by it in order to get the maximum result. If the ith number is negative, then we use the current minimum number multiple by it to get the maximum result. Therefore, no matter the ith number is positive or negative, we can get the maximum result by curMax = max(nums[i], curMax * nums[i], curMin * nums[i]). Similarlly, we can get the minimum result by curMin = min(nums[i], curMax * nums[i], curMin * nums[i]). After getting curMax and curMin, we will update the result res = max(res, curMax).

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProduct(int[] nums) {
        int res = nums[0];
        int curMax = nums[0], curMin = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int temp = curMax;
            curMax = Math.max(nums[i], Math.max(curMax*nums[i], curMin*nums[i]));
            curMin = Math.min(nums[i], Math.min(temp*nums[i], curMin*nums[i]));
            res = Math.max(res, curMax);
        }

        return res;
    }
}