算法描述：

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: 6Explanation: [2,3] has the largest product 6.

Example 2:

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

解题思路：用动态规划求解。最小值（最大值）分三种情况：当前值，当前值乘以前一个最小值（最大值），以及当前值乘以前一个最大值（最小值）。递推式为：

minVale[i] = min(min(nums[i],nums[i]*maxValue[i-1]),nums[i]*minValue[i-1]);

maxVale[i] = max(max(nums[i],nums[i]*maxValue[i-1]),nums[i]*minValue[i-1]);

内存空间还可以压缩。

int maxProduct(vector
     
      & nums) {        if(nums.size()==0) return 0;        if(nums.size()==1) return nums[0];        vector
      
        minVal(nums.size(),0);        vector
       
         maxVal(nums.size(),0);                minVal[0] = min(nums[0],0);        maxVal[0] = max(nums[0],0);                int res = maxVal[0];                for(int i=1; i < nums.size(); i++){            minVal[i] = min(min(nums[i], nums[i]*maxVal[i-1]),minVal[i-1]*nums[i]);            maxVal[i] = max(max(nums[i], nums[i]*minVal[i-1]),maxVal[i-1]*nums[i]);            if(res < maxVal[i])                res = maxVal[i];        }        return res;    }