152. Maximum Product Subarray

Posted on Edited on In

152. Maximum Product Subarray

Description

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

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

Example 2:

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

Constraints:

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

Hints/Notes

Solution

Language: C++

Cleaner solution with dp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> maxVal(n), minVal(n);
        maxVal[0] = minVal[0] = nums[0];
        for (int i = 1; i < n; i++) {
            int x = nums[i];
            maxVal[i] = max({x, maxVal[i - 1] * x, minVal[i - 1] * x});
            minVal[i] = min({x, maxVal[i - 1] * x, minVal[i - 1] * x});
        }
        return ranges::max(maxVal);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size(), res = INT_MIN;
        for (int i = 0; i < n; ) {
            if (nums[i] == 0) {
                res = max(nums[i++], res);
                continue;
            }
            int start = i;
            while (i < n && nums[i] != 0) {
                i++;
            }
            res = max(res, maxP(start, i - 1, nums));
        }
        return res;
    }

    int maxP(int start, int end, vector<int>& nums) {
        if (start == end) {
            return nums[start];
        }
        int res = 1;
        for (int i = start; i <= end; i++) {
            res *= nums[i];
        }
        if (res > 0) {
            return res;
        }
        int cur = 1, res1, res2;
        for (int i = start; i <= end; i++) {
            cur *= nums[i];
            if (nums[i] < 0) {
                res1 = res / cur;
                break;
            }
        }
        cur = 1;
        for (int i = end; i >= start; i--) {
            cur *= nums[i];
            if (nums[i] < 0) {
                res2 = res / cur;
                break;
            }
        }
        return max(res1, res2);
    }
};