Maximum Product Subarray

这题和Maximum subarray很相似，一看到就想到是一个DP问题，首先给出题目：

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

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

Example 2:

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

这题(mps)比Maximum subarray(ms)难的地方在于，乘积有很多种情况，负数乘以负数会获得正数，所以某个点假如是负数，那么下一个点就可能是正数了，所以我们不仅要保存[0,n]这个区间某个子串的最大乘积，也要保存[0,n]这个子串的最小乘积。

我们定义2个变量prevMax以及prevMin，分别保存到前一个位置的子串最大以及最小的乘积，初始化为nums[0]。然后不断的计算nums[i]、nums[i]*prevMin、nums[i]*prevMax的结果，然后分别置换到以当前点为结束点的最大以及最小值。同时维护一个全局的最大值变量，不断的和每次的最大值进行比较来交换值。

下面贴出实现：

int maxProduct(vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }
    int prevMin = nums[0];
    int prevMax = nums[0];
    int maxVal = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        int v1 = nums[i];
        int v2 = prevMin * v1;
        int v3 = prevMax * v1;
        prevMin = std::min(v1, v2);
        prevMin = std::min(prevMin, v3);
        prevMax = std::max(v1, v2);
        prevMax = std::max(prevMax, v3);
        if (prevMax > maxVal) {
            maxVal = prevMax;
        }
    }
    return maxVal;
}