152. Maximum Product Subarray

dp O(n) time O(1) space
看到这道题首先应该想到53. Maximum Subarray所以是dp
难点在于乘积受负数影响，只找最大乘积是行不通的，比较tricky的地方是要维护最大乘积和最小乘积，然后分情况对正负数进行讨论，讨论的思路和求最大和一致
mn和mx分别表示以x为结尾的连续子数组的最小和最大值

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        long mn = 1, mx = 1, res = LONG_MIN;
        for (long x : nums) {
            if (x < 0) {
                long t = mn;
                mn = min(x, mx * x);
                mx = max(x, t * x);
            } else {
                mn = min(x, mn * x);
                mx = max(x, mx * x);
            }
            res = max(res, mx);
        }
        return res;
    }
};