算法描述:
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.
解题思路:用动态规划求解。最小值(最大值)分三种情况:当前值,当前值乘以前一个最小值(最大值),以及当前值乘以前一个最大值(最小值)。递推式为:
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<int>& nums) { if(nums.size()==0) return 0; if(nums.size()==1) return nums[0]; vector<int> minVal(nums.size(),0); vector<int> 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; }