给定一个数组，获取数组中子数组的最大乘积。
思考：最初想到的就是暴力求解方法，时间复杂度O(n^2)枚举出所有解，最终得到最大乘积。看了discuss中发现有更好的解法。动态规划，用两个变量当前的极大值和极小值，因为后面乘以一个负数的话，极大值会变成极小值，而再乘以一个负数又会变成极大值。所以中间过程中只需要记录这两个值即可。
解法：
int maxProduct(vector<int>& nums) { if (nums.empty()) { return -1; } if (nums.size() == 1) { return nums[0]; } int gmax = nums[0]; int max = nums[0]; int min = nums[0]; // 每次保留到当前元素的极大乘积和极小乘积 // 不需要dp[n]保存之前的所有状态 for (int i = 1; i < nums.size(); ++i) { int x = nums[i]; max *= x; min *= x; if (max < min) { swap(max, min); } // 下面一行等价于 max = max(dp[i - 1] * nums[i], nums[i]); // 当前的值乘到前面去，或是从当前位置起，取最大值 if (max < x) { max = x; } // 下面一行等价于 min = min(dp[i - 1] * nums[i], nums[i]); // 当前的值乘到前面去，或是从当前位置起，取最小值 if (min > x) { min = x; } if (gmax < max) { gmax = max; } } return gmax; }
