济南h5网站建设温州网站建设钢筋工

一个子数组问题，我们要使用线性dp，最好先考虑以i结尾，如果定义dp[i]为前i个数最大子数组乘积值 那么dp[i-1]就无法转移到dp[i]。因此我们先考虑dp[i]定义为以第i个数结尾的最大子数组乘积值。

 53. 最大子数组和

最大子数组和是一个动态规划问题，定义dp[i]表示以nums[i]结尾的最大子数组和，那么dp[i]=max(dp[i-1]+nums[i],nums[i])。对于这里乘积最大子数组和，我们也有这样的想法，但是由于负负得正，如{-3,2,3,-2}，dp[2]=6，nums[3]=-2，但是dp[3]不是-2，而应当乘以前面的-3。

记录前一个负数位置的动态规划

一个朴素的想法就是：

        记录前一个负数的位置，这样遍历到一个负数时，我们在前一个负数到这个负数之间的数都是≥0的，这样在遇到负数时的连乘最大值应当至少是前一个负数连乘到这个负数，而当 以 前一个负数的 前一个数为结尾的子数组乘积为正时，也应该考虑进去。这样负数的情况就考虑完了。当之前没有负数时，有0时dp[i]就是0，没有0时dp[i]就是该负数。

        当遇到的是一个正数，则只需要使用dp[i]=max(dp[i-1]*nums[i],nums[i])，因为以该正数结尾的最大连乘，要么是本身，要么以 前一个数结尾的子数组连乘为正*该正数。

class Solution {
public:int maxProduct(vector<int>& nums) {vector<int> dp(nums.size());int ans;ans=dp[0]=nums[0];int minus=-1;if(nums[0]<0) minus=0;int flag=0;//记录前一个负数到这个负数是否存在0for(int i=1;i<nums.size();++i){dp[i]=1;if(nums[i]==0) flag=1;if(nums[i]<0){if(minus>=0){//中间有0也应该是0if(minus>0&&dp[minus-1]>0)dp[i]=dp[minus-1]*nums[minus]*nums[i];else dp[i]=nums[minus]*nums[i];if(minus!=i-1) {if(dp[minus]<=0)dp[i]*=dp[i-1];else dp[i]*=dp[i-1]/dp[minus];}if(flag) dp[i]=0;}else dp[i]=nums[i];minus=i;flag=0;}else dp[i]=dp[i-1]>0?dp[i-1]*nums[i]:nums[i];if(dp[i]>ans) ans=dp[i];}//cout<<dp[nums.size()-2];return ans;}
};
//dp[i]表示以i结尾的子数组的乘积最大值

记录最大最小的动态规划

进阶的考虑：

        当遇到负数时，我们能不能让 以它前一个数结尾的连乘 负得更多，这样我们再乘上这个数就大的更多。

        当遇到正数时，我们依然让 以前一个数结尾的连乘 正的更多即可。

因此，我们可以保存一个最小值和最大值。

最小值让以第i个数结尾的子数组连乘最小，

最大值让以第i个数结尾的子数组连乘最大，

最小值的计算和最大值的计算，前一两者同时考虑就把正负给抵消掉了。

class Solution {
public:int maxProduct(vector<int>& nums) {int mx=nums[0];int mn=nums[0];int ans=nums[0];for(int i=1;i<nums.size();++i){int Max=mx,Min=mn;mx=max(max(Max*nums[i],Min*nums[i]),nums[i]);mn=min(min(Min*nums[i],Max*nums[i]),nums[i]);ans=ans>mx?ans:mx;}return ans;}
};