152-maximum-product-subarray.md

152. Maximum Product Subarray - 乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

---

题目标签：Array / Dynamic Programming

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
cpp	4 ms	1.4 MB

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int pre = nums[0] < 0 ? 0 : -1;
        for (int i=1; i<nums.size(); ++i) {
            if (nums[i] >= 0) {
                dp[i] = max(nums[i], nums[i] * dp[i-1]);
            } else {
                if (pre != -1) {
                    int k = 1;
                    for (int j=pre; j<=i; ++j) {
                        k *= nums[j];
                    }
                    dp[i] = max(k, k * dp[pre-1]);
                }
                pre = i;
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};
static auto _ = [](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();