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.
由于负数的存在，需要同时保存当前最大值和当前最小值，所以需要维护两个DP表，可以分别表示为dp_min和dp_max。所以即为dp_max里的最大值。
需要维护的当前最大值和当前最小值，都是在dp_min[i-1] * A[i]，dp_max[i] * A[i]，和A[i]这三者里面取一即可。有了这个只关乎最终状态，不关乎过程细节的结论，解题过程可以大大简化。
1 class Solution { 2 public: 3 int maxProduct(vector<int>& nums) { 4 int n = nums.size(); 5 if(n==0) return 0; 6 vector<int>dp_max(n,nums[0]); 7 vector<int>dp_min(n,nums[0]); 8 9 int res_val = nums[0]; 10 for(int i =1;i<n;i++){ 11 dp_max[i] = std::max( std::max(dp_max[i-1]*nums[i],dp_min[i-1]*nums[i]), nums[i]); 12 dp_min[i]= std::min( std::min(dp_min[i-1]*nums[i],dp_max[i-1]*nums[i]), nums[i]); 13 res_val =std::max(res_val,dp_max[i]); 14 } 15 16 return res_val; 17 18 } 19 };
原文：https://www.cnblogs.com/zle1992/p/10415601.html