LeetCode OJ：Maximum Product Subarray（子数组最大乘积）

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

很显然是一个动态规划的问题，找到递归表达式就可以了，考虑到会有负负相乘的问题，所以应该维持一个最大的值以及一个最小的值，递归表达式如下所示：

1 maxLocal[i + 1] = max(max(maxLocal[i] * nums[i + 1], minLocal[i] * nums[i + 1]), nums[i + 1]);
2 minLocal[i + 1] = min(min(maxLocal[i] * nums[i + 1], minLocal[i] * nums[i + 1]), nums[i + 1]);
3 maxGlobal[i + 1] = max(maxGlobal[i], maxLocal[i + 1]);

代码如下所示：

 1 class Solution {
 2 public:
 3     int maxProduct(vector<int>& nums) {
 4         int sz = nums.size();
 5         if (sz == 0)return 0;
 6         if (sz == 1)return nums[0];
 7         int maxP, minP, a, b, ret;
 8         ret = maxP = minP = a = b = nums[0];
 9         for (int i = 1; i < sz; ++i){
10             a = max(maxP * nums[i], minP * nums[i]);
11             b = min(maxP * nums[i], minP * nums[i]);
12             maxP = max(a, nums[i]);
13             minP = min(b, nums[i]);
14             ret = max(maxP, ret);
15         }
16         return ret;
17     }
18 
19 };

java版本的如下所示，注意使用两个中间变量的原因是防止maxVal先直接更新了之后又被minVal所误用：

 1 public class Solution {
 2     public int maxProduct(int[] nums) {
 3         int maxVal, minVal, ret, tmpMax, tmpMin;
 4         maxVal = minVal = ret = tmpMax = tmpMin = nums[0];
 5         for(int i = 1; i < nums.length; ++i){
 6             tmpMax = Math.max(maxVal * nums[i], minVal * nums[i]);
 7             tmpMin = Math.min(maxVal * nums[i], minVal * nums[i]);
 8             maxVal = Math.max(tmpMax, nums[i]);
 9             minVal = Math.min(tmpMin, nums[i]);
10             ret = Math.max(maxVal, ret);
11         }
12         return ret;
13     }
14 }