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.

 

解题思路：乘法与加法最大差别在于，当前元素的符号具有全局性的作用。

如果当前元素为负，那么连乘到上个元素的最大乘积，再乘以当前元素，就变成负数，甚至可能成为最小乘积。

同样，连乘到上个元素的最小乘积如为负，再乘以当前元素，就变成正数，甚至可能成为最大乘积。

 

因此使用动态规划的方法：

记maxLast/minLast为连乘到上个元素的最大/小乘积

记maxCur/minCur为连乘到当前元素的最大/小乘积

记maxAll为全局最大乘积

 

class Solution {public:    int maxProduct(vector
     
      & nums) {        if(nums.empty())            return 0;        if(nums.size() == 1)            return nums[0];                    int maxAll = nums[0];       //global maximum        int maxLast = nums[0];      //maximum including last element        int maxCur;                 //maximum including current element        int minLast = nums[0];      //minimum including current element        int minCur;                 //minimum including last element        for(int i = 1; i < nums.size(); i ++)        {            maxCur = max(nums[i], max(maxLast*nums[i], minLast*nums[i]));            minCur = min(nums[i], min(maxLast*nums[i], minLast*nums[i]));            maxLast = maxCur;            minLast = minCur;            maxAll = max(maxAll, maxCur);        }        return maxAll;    }};