5,8,−3,4,−3
dp_max=[5,(40,40,8)=40,(-120,-24,-3)=-3 ,(-12,-480,4)=4 ,(-12,1440,-3)=1440]
dp_min=[5,(40,40,8)=8 ,(-120,-24,-3)=-120,(-12,-480,4)=-480,(-12,1440,-3)=-12]
考虑当前位置如果是一个负数的话,那么我们希望以它前一个位置结尾的某个段的积也是个负数,这样就可以负负得正,并且我们希望这个积尽可能「负得更多」,即尽可能小。如果当前位置是一个正数的话,我们更希望以它前一个位置结尾的某个段的积也是个正数,并且希望它尽可能地大。
dp_max记录当前位置为i时,最大的连续正数乘积。
dp_min记录当前位置为i时,最大的连续负数乘积。
一直记录dp_min,就是等两个负号出现时,dp_max通过dp_min翻盘。
class Solution {
public:
int maxProduct(vector<int>& nums) {
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]));
}
for_each(maxF.begin(), maxF.end(), [](int& val){cout<<val<<endl;});
cout<<"-------------"<<endl;
for_each(minF.begin(), minF.end(), [](int& val){cout<<val<<endl;});
return *max_element(maxF.begin(), maxF.end());
}
};