152. Maximum Product Subarray

當前的數組最大值有三種可能, 如果一路都是正整數, 那乘過來只會越乘越大, 問題是會出現負數, 這三種可能分別是

1. 自己本身, 因為上一個值是正的, 如果乘上負數就會變極小
2. 當前值繼續累乘最大
3. 當前值乘上累乘最小

為什麼會有最小, 倘若一個最小的值, 乘上負數後, 很有機會翻盤

所以我們也要記錄最小值

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.empty()) return 0;
        int res = nums[0];
        int mn = nums[0];
        int mx = nums[0];
        for(int i = 1; i < nums.size();i++){
            int tmax = mx, tmin = mn;
            mx = max({nums[i], tmax * nums[i], tmin * nums[i]});
            mn = min({nums[i], tmax * nums[i], tmin * nums[i]});
            res = max(res , mx);
            
        }
        return res;
    }
};