152. Maximum Product Subarray

解題思路

題目敘述讓我想到之前寫過 53. Maximum Subarray 這題，只是變成乘積最大。

一樣另外開陣列，存當下那個數的 subarray 最大能多少。但乘法與加法不一樣，兩個負數相乘會變回正，所以也要存最負 array。

程式碼

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int> maxArr(nums.size(), 0);
        vector<int> minArr(nums.size(), 0);
        maxArr[0] = nums[0];
        minArr[0] = nums[0];

        int maxP = maxArr[0];
        for(int i=1; i<nums.size(); i++)
        {
            maxArr[i] = max({nums[i], maxArr[i-1] * nums[i], minArr[i-1] * nums[i]});
            minArr[i] = min({nums[i], maxArr[i-1] * nums[i], minArr[i-1] * nums[i]});
            maxP = max(maxP, maxArr[i]);
        }
        return maxP;
    }
};