leetcode-152 乘積最大子序列

題目描述：

給定一個整數數組 nums ，找出一個序列中乘積最大的連續子序列（該序列至少包含一個數）。

示例 1:

輸入: [2,3,-2,4]

輸出: 6

解釋: 子數組 [2,3] 有最大乘積 6。

示例 2:

輸入: [-2,0,-1]

輸出: 0

解釋: 結果不能為 2, 因為 [-2,-1] 不是子數組。

該題目求最大子序列的乘積，參考​​leetcode-52 最大子序和​​中的暴力解法，窮舉所有元素的可能性：

int maxSubArray(vector<int>& nums) {
    if(nums.size() == 1) return nums[0];

    int res = nums[0];
    for (int i = 1;i < nums.size(); ++i) {
        int pre = _maxSubArray(nums,i);
        res = max(res,pre);
    }

    return res;
}
int _maxSubArray(vector<int> &nums, int index) {
    if(index == 0) {
        return nums[0];
    }

    int pre = _maxSubArray(nums, index - 1);
    int res = max(nums[index] * pre, nums[index]);

    return res;
}      

但是和的形态和積的形态還是有差異的，針對-2 2 -3的數列，以上方法求的最大乘積為2，但是實際上是12

乘積存在 之前的最小值（負數）再乘上目前的一個負數，就有可能變為最大值。

• dp_max[i] = max(dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i], nums[i])
• dp_min[i] = min(dp_max[i-1] * nums[i], dp_min[i-1] * nums[i], nums[i])

int maxProduct(vector<int>& nums) {
    if(nums.size() == 1) return nums[0];

    int dp[2][2],res; //僅僅需要常數的空間，每個方程僅需要儲存目前狀态和前一個狀态

    dp [0][0] = nums[0]; //最大值的方程
    dp [0][1] = nums[0]; //最小值的方程
    res = nums[0];

    for (int i = 1;i < nums.size(); ++i) {
        int x = i % 2; //轉換下标
        int y = (i - 1) % 2;
        dp[x][0] = max(max(dp[y][0] * nums[i], dp[y][1] * nums[i]),nums[i]);
        dp[x][1] = min(min(dp[y][0] * nums[i], dp[y][1] * nums[i]),nums[i]);

        res = std::max(res, dp[x][0]);
    }

    return res;
}