一個(gè)子數(shù)組問(wèn)題，我們要使用線性dp，最好先考慮以i結(jié)尾，如果定義dp[i]為前i個(gè)數(shù)最大子數(shù)組乘積值?那么dp[i-1]就無(wú)法轉(zhuǎn)移到dp[i]。因此我們先考慮dp[i]定義為以第i個(gè)數(shù)結(jié)尾的最大子數(shù)組乘積值。

?53. 最大子數(shù)組和

最大子數(shù)組和是一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題，定義dp[i]表示以nums[i]結(jié)尾的最大子數(shù)組和，那么dp[i]=max(dp[i-1]+nums[i],nums[i])。對(duì)于這里乘積最大子數(shù)組和，我們也有這樣的想法，但是由于負(fù)負(fù)得正，如{-3,2,3,-2}，dp[2]=6，nums[3]=-2，但是dp[3]不是-2，而應(yīng)當(dāng)乘以前面的-3。

記錄前一個(gè)負(fù)數(shù)位置的動(dòng)態(tài)規(guī)劃

一個(gè)樸素的想法就是：

????????記錄前一個(gè)負(fù)數(shù)的位置，這樣遍歷到一個(gè)負(fù)數(shù)時(shí)，我們?cè)谇耙粋€(gè)負(fù)數(shù)到這個(gè)負(fù)數(shù)之間的數(shù)都是≥0的，這樣在遇到負(fù)數(shù)時(shí)的連乘最大值應(yīng)當(dāng)至少是前一個(gè)負(fù)數(shù)連乘到這個(gè)負(fù)數(shù)，而當(dāng)?以 前一個(gè)負(fù)數(shù)的 前一個(gè)數(shù)為結(jié)尾的子數(shù)組乘積為正時(shí)，也應(yīng)該考慮進(jìn)去。這樣負(fù)數(shù)的情況就考慮完了。當(dāng)之前沒(méi)有負(fù)數(shù)時(shí)，有0時(shí)dp[i]就是0，沒(méi)有0時(shí)dp[i]就是該負(fù)數(shù)。

? ? ? ? 當(dāng)遇到的是一個(gè)正數(shù)，則只需要使用dp[i]=max(dp[i-1]*nums[i],nums[i])，因?yàn)橐栽撜龜?shù)結(jié)尾的最大連乘，要么是本身，要么以 前一個(gè)數(shù)結(jié)尾的子數(shù)組連乘為正*該正數(shù)。

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;//記錄前一個(gè)負(fù)數(shù)到這個(gè)負(fù)數(shù)是否存在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也應(yīng)該是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結(jié)尾的子數(shù)組的乘積最大值

記錄最大最小的動(dòng)態(tài)規(guī)劃

進(jìn)階的考慮：

? ? ? ? 當(dāng)遇到負(fù)數(shù)時(shí)，我們能不能讓 以它前一個(gè)數(shù)結(jié)尾的連乘 負(fù)得更多，這樣我們?cè)俪松线@個(gè)數(shù)就大的更多。

? ? ? ? 當(dāng)遇到正數(shù)時(shí)，我們依然讓?以前一個(gè)數(shù)結(jié)尾的連乘 正的更多即可。

因此，我們可以保存一個(gè)最小值和最大值。

最小值讓以第i個(gè)數(shù)結(jié)尾的子數(shù)組連乘最小，

最大值讓以第i個(gè)數(shù)結(jié)尾的子數(shù)組連乘最大，

最小值的計(jì)算和最大值的計(jì)算，前一兩者同時(shí)考慮就把正負(fù)給抵消掉了。

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;}
};

?

?