前言

子數組最大累加和問題看似簡單，但能延伸出的題目非常多，千題千面，而且會和其他算法結合出現。

一、最大子數組和

class Solution {
public:int maxSubArray(vector<int>& nums) {int n=nums.size();vector<int>dp(n);//i位置往左能延伸出的最大累加和dp[0]=nums[0];int ans=dp[0];for(int i=1;i<n;i++){dp[i]=max(nums[i],dp[i-1]+nums[i]);ans=max(ans,dp[i]);}return ans;}//擴展問題：//求子數組最大累加和的left、right和sumint left;int right;int sum;void extra(vector<int>&nums){sum=INT_MIN;for(int l=0,r=0,pre=INT_MIN;r<nums.size();r++){if(pre>=0)//前面累加和收益為正 -> 不換開頭{pre+=nums[r];}else//換開頭{pre=nums[r];l=r;}if(pre>sum)//更新{sum=pre;left=l;right=r;}}}
};

這個就是經典的子數組最大累加和問題，這個和擴展問題求left和right非常重要，是整個子數組最大累加和專題的基礎！！

對于dp表的定義就是必須以i位置結尾，往左的子數組最大累加和。那么對于每個位置，都是當前的數加上要之前的和不要之前的兩種情況。

那么如果要求這個子數組的left和right，整體過程類似滑動窗口，就是在空間壓縮的基礎上，如果之前的累加和大于等于零，說明收益是正的，那就保留之前的，否則就不要之前的，然后把l更新到r位置。當累加和能更新最大值，就連著left和right一起更新。

二、打家劫舍

class Solution {
public:int rob(vector<int>& nums) {int n=nums.size();if(n==1){return nums[0];}if(n==2){return max(nums[0],nums[1]);}vector<int>dp(n);dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(int i=2;i<n;i++){dp[i]=max(dp[i-1],max(nums[i],dp[i-2]+nums[i]));//dp[i]=max(dp[i-1],dp[i-2]+nums[i]);}return dp[n-1];}
};

這個題首先要注意的就是特例，當只有一間或者兩間的話直接返回。

之后就是分情況討論，如果上間偷了，這間就不能偷，那么依賴的就是dp[i-1]；如果上間沒偷，那么就還有要之前的和不要之前的兩種情況，最后取三種情況最大值即可。

其實因為這個題每間房子的收益都是大于零的，那么就不用討論不要之前的這種情況了。

三、環形子數組的最大和

class Solution {
public:int maxSubarraySumCircular(vector<int>& nums) {int n=nums.size();int sum=nums[0],maxSum=nums[0],minSum=nums[0];int maxpre=nums[0],minpre=nums[0];for(int i=1;i<n;i++){sum+=nums[i];//統計總累加和maxpre=max(nums[i],maxpre+nums[i]);maxSum=max(maxSum,maxpre);minpre=min(nums[i],minpre+nums[i]);minSum=min(minSum,minpre);}return sum==minSum?maxSum:max(maxSum,sum-minSum);//防止都扣掉}
};

這個題就需要點轉化了，轉化的思路就是，由于是環形數組，那么在其中刪除任意一段子數組，剩下的仍連續，那么就可以將最大累加和轉化成總體累加和減去最小的累加和和最大累加和的最大值。

整體的依賴關系還是要之前的和不要之前的，但這里要統計最大累加和和最小累加和。注意，若整體累加和等于最小累加和，為了防止把數全扣了，此時要返回最大累加和，否則就是最大累加和和相減后的最大值。

四、打家劫舍 II

class Solution {
public:int rob(vector<int>& nums) {int n=nums.size();if(n==1){return nums[0];}vector<int>dp(n);//不偷第0間 -> 1~n-1dp[0]=0;dp[1]=nums[1];for(int i=2;i<=n-1;i++){dp[i]=max(dp[i-1],max(nums[i],dp[i-2]+nums[i]));}int p1=dp[n-1];//偷第0間 -> nums[0]+2~n-2fill(dp.begin(),dp.end(),0);dp[0]=nums[0];dp[1]=nums[0];//注意！！！只偷第0間時dp[