LeetCode 152 Maximum Product Subarray
概述
https://leetcode.com/problems/maximum-product-subarray/
动态规划法
等等，子问题的最优解未必可用啊，我感觉我们应当存两个，一个最大的，一个最小的。
我去，AC 了，哈哈哈哈哈
class Solution {
public:
int maxProduct(vector<int>& nums) {
auto maxdp = nums;
auto mindp = nums;
int ans = nums.back();
for (int i = nums.size() - 2; i >= 0; i --) {
maxdp[i] = max(nums[i], max(nums[i] * maxdp[i+1], nums[i] * mindp[i+1]));
mindp[i] = min(nums[i], min(nums[i] * maxdp[i+1], nums[i] * mindp[i+1]));
ans = max(ans, maxdp[i]);
}
return ans;
}
};