152. Maximum Product Subarray

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

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.

這題可以用DP來做，維護一個2D array dp，dp[i][0]代表到nums[i]的product最小值，dp[i][1]代表到nums[i]的product的最大值。因為數字可能有正有負，遇到負的值時，就有可能搭配上最小值之後反而變成最大的，而搭配上最大值反而變成最小的。也有可能遇到0的情形，所以如果前面都是0，突然來一個正值，那就要不管前面的乘積直接從當前這個非零的正數開始。

int maxProduct(vector<int>& nums) { // time: O(n); space: O(n)
    if (nums.empty()) return 0;
    int n = nums.size();
    vector<vector<int> > dp(n, vector<int>(2, 0));
    dp[0][0] = nums[0];
    dp[0][1] = nums[0];
    int res = nums[0];
    for (int i = 1; i < n; ++i) {
        dp[i][0] = min({nums[i], nums[i] * dp[i - 1][0], nums[i] * dp[i - 1][1]});
        dp[i][1] = max({nums[i], nums[i] * dp[i - 1][0], nums[i] * dp[i - 1][1]});
        res = max(res, dp[i][1]);
    }
    return res;
}

遇到負值時原本的最大最小值就會反過來，所以直接swap。

int maxProduct(vector<int>& nums) { // time: O(n); space: O(1)
    if (nums.empty()) return 0;
    int n = nums.size();
    int res = nums[0];
    for (int i = 1, mn = res, mx = res; i < n; ++i) {
        if (nums[i] < 0) swap(mn, mx);
        mn = min(nums[i], nums[i] * mn);
        mx = max(nums[i], nums[i] * mx);
        res = max(res, mx);
    }
    return res;
}