LeetCode 152. Maximum Product Subarray [Medium] [C++] 解題筆記

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

 

Example 1:

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

Example 2:

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

想法:

    這題跟 53. Maximum Subarray 有點像但是 53 題是求和不是乘積所以單純許多，這題因為是乘積所以不能單純

紀錄之前的最大值然後跟當前位置做比較，除了最大值之外還需要另外儲存之前的最小值(最小值若是負數有可能跟之後的負數相乘後

變得比當前最大值還大)。因此我們可以宣告兩個 DP array cur_max 與 cur_min 分別表示在 nums[0]~nums[i](包含 nums[i])

時最大/最小的 subarray 乘積，那摸在 nums[0]~nums[i + 1](包含 nums[i+1])時最大/最小的 subarray 乘積就會是

cur_max[i]*nums[i + 1] or cur_min[i]*nums[i + 1] or nums[i + 1] 這三個數中的最大/最小值，最後只要在每次

找完cur_max之後更新當前找到的最大值即可。

完整程式碼:

解法一:O(n) time, O(n) space

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        // 表示 0~i 包含 nums[i] 的最大 subarray 乘積
        vector<int> cur_max(nums.size(), 0);
        // 表示 0~i 包含 nums[i] 的最小 subarray 乘積
        vector<int> cur_min(nums.size(), 0);
        int res = nums[0];
        cur_max[0] = nums[0];
        cur_min[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            cur_max[i] = max(max(cur_max[i - 1] * nums[i], cur_min[i - 1] * nums[i]), nums[i]);
            cur_min[i] = min(min(cur_max[i - 1] * nums[i], cur_min[i - 1] * nums[i]), nums[i]);
            res = max(cur_max[i], res);
        }
        return res;
    }
};

解法二:(space optimize) O(n) time, O(1) space    

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = nums[0];
        int cur_max = nums[0];
        int cur_min = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int tmp_max = cur_max;
            int tmp_min = cur_min;
            cur_max = max(max(tmp_max*nums[i], tmp_min*nums[i]), nums[i]);
            cur_min = min(min(tmp_max*nums[i], tmp_min*nums[i]), nums[i]);
            res = max(res, cur_max);
        }
        return res;
    }
};