最大子数组和的状态转移方程是dp[i]=max(dp[i-1]+nums[i],nums[i]) 其中dp[i]表示以nums[i]结尾的最大子数组的和。所以以nums[i]结尾的最大子数组和无非就是要么加入前边的要么单独自己。
但是乘积最大子数组不满足这样的转移方程 dp[i]不一定是由dp[i-1]来决定的。
再维护一个最小乘积的数组，因为nums[i]可能为正也可能为负，求最大值就是在min[i-1]*nums[i],nums[i]，max[i-1]*nums[i]中选最大的。有了最大和最小两个数组可以把结果一直积累下去。
class Solution {
public:
int maxProduct(vector<int>& nums) {
//还可以这么初始化一个vector 因为maxF[0]和minF[0]都是第一个数
vector <int> maxF(nums), minF(nums);
for (int i = 1; i < nums.size(); ++i) {
maxF[i] = max(maxF[i - 1] * nums[i], max(nums[i], minF[i - 1] * nums[i]));
minF[i] = min(minF[i - 1] * nums[i], min(nums[i], maxF[i - 1] * nums[i]));
}
return *max_element(maxF.begin(), maxF.end());
}
};
TRANSLATE with