leetcode-152-Maximum Product Subarray

Posted on | In , | |
Words count in article: 540 | Reading time ≈ 2

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
求连续子数组最大乘积。

1
2
3
4
5
6
7
8
9
10
Example 1:

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

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
双重循环(O(n^2))
遍历每个区间的开始和结束位置，然后求这个区间的积，然后保留最大的积即可。
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        const int N = nums.size();
        int res = INT_MIN;
        for (int i = 0; i < N; ++i) {
            int cur = 1;
            for (int j = i; j < N; ++j) {
                if (j == i)
                    cur = nums[i];
                else 
                    cur = cur * nums[j];
                res = max(res, cur);
            }
        }
        return res;
    }
};
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
动态规划
因为某个位置可能出现了0或者负数。当遇到0的时候，整个乘积会变成0；当遇到负数的时候，当前的最大乘积会变成最小乘积，最小乘积会变成最大乘积。

有上面的分析可以看出，必须使用两个数组分别记录以某个位置i结尾的时候的最大乘积和最小乘积了。令最大乘积为f，最小乘积为g。那么有：

当前的最大值等于已知的最大值、最小值和当前值的乘积，当前值，这三个数的最大值。
当前的最小值等于已知的最大值、最小值和当前值的乘积，当前值，这三个数的最小值。
结果是最大值数组中的最大值。

时间复杂度是O(N)，空间复杂度是O(N). N是数组大小。
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        const int N = nums.size();
        vector<int> mx(N);
        vector<int> mn(N);
        int res = mx[0] = mn[0] = nums[0];
        for (int i = 1; i < N; ++i) {
            mx[i] = max(nums[i], max(mx[i - 1] * nums[i], mn[i - 1] * nums[i]));
            mn[i] = min(nums[i], min(mx[i - 1] * nums[i], mn[i - 1] * nums[i]));
            res = max(mx[i], res);
        }
        return res;
    }
};
事实上可以使用判断，直接知道怎么优化。当nums[i]为正的时候，那么正常更新。如果nums[i]<=0的时候，需要反向更新。
Donate? comment?