152. Maximum Product Subarray

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.

---

本题要求一个数组中最大的连续子数组的积，和LeetCode Maximum Subarray很类似，后者是求最大连续子数组的和。
但是因为乘积有其独特性，即负负得正，所以即使前面算到有很大的负数，也不能舍弃，万一后面来一个负数，负负得正就会得到很大的正数。
本题也是使用动态规划来做。维护两个变量，令curMax和curMin分别表示当前最大连续乘积值和最小连续乘积值。则有
curMax = max(curMax*nums[i], curMin*nums[i], nums[i]);
curMin = min(curMax*nums[i], curMin*nums[i], nums[i]);
很好理解，不解释：

class Solution {
  public: int maxProduct(vector < int > & nums) {
    int ans = nums[0], curMax = nums[0], curMin = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
      int tmp = curMax;
      curMax = max(max(curMax * nums[i], curMin * nums[i]), nums[i]);
      curMin = min(min(tmp * nums[i], curMin * nums[i]), nums[i]);
      ans = max(ans, curMax);
    }
    return ans;
  }
};

本代码提交AC，用时6MS。

再细究一下，假设curMax和curMin为当前最大最小连续乘积值，且规定curMax一定是正数。则当nums[i]为正数时，curMax更新为curMax*nums[i]，无论curMin是否为正，curMin都更新为curMin*nums[i]。
当nums[i]为负数时，curMax更新为curMin*nums[i]，curMin更新为curMax*nums[i]。因为curMax一定为正，所以curMax*nums[i]一定为负。即使curMin也为正，但curMin<curMax，所以curMin*nums[i]>curMax*nums[i]。如果curMin为负，则curMin*nums[i]为正，更大于curMax*nums[i]了。
这种思路就分析得比较细致，注意代码第6行需要记录前一次的最大值，因为运算过程中curMax有可能是0或者负数，为了保证curMax一定是正数的性质，需要第6行（比如输入为0,2，则i=0运算完之后curMax=curMin=0；当i=1时，如果第8行curMax*=nums[i]，则curMax还是0）。且因为第12行会更新curMax，而第13行需要用到上一次的最大值。
完整代码如下：

class Solution {
  public: int maxProduct(vector < int > & nums) {
    int ans = nums[0], curMax = 1, curMin = 1;
    for (size_t i = 0; i < nums.size(); ++i) {
      int oldMax = max(curMax, 1);
      if (nums[i] > 0) {
        curMax = oldMax * nums[i];
        curMin *= nums[i];
      } else {
        curMax = curMin * nums[i];
        curMin = oldMax * nums[i];
      }
      ans = max(ans, curMax);
    }
    return ans;
  }
};

本代码提交AC，用时也是6MS。