解析：每次看到动态规划就有点懵，哎~，明明知道是动态规划，就是想不到怎么建立动态转移方程。以为例： 2 3 -2 4 1 分析 比较容易想到的是，依次查找[2] [2 3] [2 3 -2] [2 3 -2 4] [3] [3 -2] [3 -2 4] [-2] [-2 4] [4]，时间复杂为O(n^2)，很明显这不是出题的本意，难点就在于0和负数的出现，当遇到0时，当前子序列的乘积就会变为0，当遇到负数时，当前子序列的乘积就会出现不同的状态，所要解决的问题就是，在数组往下推移的过程中，如何保存当前子序列的最大值同时又能记录上一个元素，参考其他博主的思路，很巧妙地用了两个dp数组分别记录当前子序列的乘积最大值和最小值，maxMul[i]表示前i个子序列中的连续子序列乘积的最大值，minMul[i]表示前i个子序列中的连续子序列乘积的最小值，动态规划的一个最主要的特点是，能够记录所有的局部最优解，只需对局部最优解进行比较，我们就可以获取全局最优解。这也是贪心算法的缺陷，容易陷入局部最优解 2 流程 i = 0 ： maxMul[0] = 2 minMul[0] = 2 res = 2 i = 1 ： maxMul[1] = 6 minMul[1] = 3 res = 6 i = 2 ： maxMul[2] = -2 minMul[2] = -12 res = 6 i = 3 ： maxMul[3] = 4 minMul[3] = -48 res = 6 从这里我们可以看到，之所以要用两个dp数组进行更新，因为不仅仅要记录当前连续子序列的乘积最大值，还要记录上一个元素的值(可能是局部最优解)
class Solution { public: int maxProduct(vector<int>& nums) { vector<int> maxMul(nums.size(), 0), minMul(nums.size(), 0); int res = nums[0]; maxMul[0] = minMul[0] = nums[0]; for (int cur = 1; cur < nums.size(); ++cur){ maxMul[cur]=max(max(maxMul[cur-1]*nums[cur], minMul[cur-1]*nums[cur]), nums[cur]); //局部最优解 minMul[cur]=min(min(maxMul[cur-1]*nums[cur], minMul[cur-1]*nums[cur]), nums[cur]); res = max(maxMul[cur], res); //全局最优解 } return res; } };第二种解法 利用两个变量分别记录当前局部最有解和当前元素，原理都是一样，只是减少了空间复杂度
class Solution { public: int maxProduct(vector<int>& nums) { int mx = nums[0], mn = nums[0], res = nums[0]; for (int cur = 1; cur < nums.size(); ++cur){ if (nums[cur] < 0){ int t = mx; mx = max(mn*nums[cur], nums[cur]); mn = min(t*nums[cur], nums[cur]); } else{ mx = max(mx*nums[cur], nums[cur]); mn = min(mn*nums[cur], nums[cur]); } res = max(res, mx); } return res; } };[1]https://www.cnblogs.com/grandyang/p/4028713.html
