经典动态规划之最大子数组和

给你一个数组：其中元素有正有负，问你最大子数组和是多少：

我们初次想到的肯定是暴力算法：通过两层for 循环去枚举每个子数组的起始和最终位置，记录所有子数组和的最大值：

ans=负无穷
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
ans=max（sum[i->j],ans]）

}

}

每次计算sum的时间复杂度是O（n）；时间复杂度太高了，可以进行优化；

对于所有子数组可以按左端点分开：以a[0],a[1]…开头的，之后计算a[i]开头的最大子数组，右端点从i到末尾，

ans=负无穷
for(int i=0;i<len;i++){
sum=0;
for(int j=i;j<len;j++){
sum+=a[j]
ans=max(ans,sum);
}

}

成功将时间复杂度降到了O（n）；

但是还是很高，时间复杂度再往下降，就要考虑动态规划的问题了；

上述的优化暴力算法是固定左端点，那能不能固定右端点呢，当然可以，不妨设dp[i]是以原数组第i'个元素结尾的子所有数组中的最大值，接下来就要看状态转移方程了：

已知以知原数组第i'个元素结尾的所有数组中最大到了第一个数组，最小只包括本身，那么就以最后第i个元素作为分界线，一种数组是只包括第i个元素的，一类数组是包括其他元素的，对于前一个就是a[i]，对于后一种一知至少有两个元素 i 和 i-1 ，那么把i单独拿出来，这一组剩下的所有数组的右端点就是i-1了，那么这些数组的最大值就是dp[i-1]+a[i]

因此dp[i]=max(a[i],dp[i-1]+a[i]);

边界显而易见就是dp[0]；

易得dp[0]=0；

好了在得到dp数组，便可遍历dp数组去找最大子数组和了

下面是一道模版题：

最大子段和

来看代码

#include<iostream>
using namespace std;
int a[200000];
int main(){
int n=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=a[1];
int dp=0;

for(int i=1;i<=n;i++){
dp=max(dp+a[i],a[i]);
ans=max(ans,dp);
}

cout<<ans;

return 0;
}

这里我进行了空间优化，因为dp数组我只需要记录前一个就够了，我要求的从来不是dp数组是里面的最大值，因此遍历原数组填充dp时ans时刻更新就够了

区间最大序列和

问题描述

现有 nn 个数形成的序列 aiai​（i∈[1,n]i∈[1,n]），给你 qq 组查询，每次查询给定一个区间 [l,r][l,r]（1≤l≤r1≤l≤r）。你需要查询出该区间最大连续子序列的和，并将其输出。

由于输入很多，cpp 请使用 scanf 与 printf。

输入格式

第一行输入一个正整数 nn。

第二行输入 nn 个正整数 aiai​。

第三行输入一个正整数 qq。

接下来 qq 行，每行输入 22 个正整数 l,rl,r。

输出格式

对于每组查询，输出该区间最大连续子序列的和。

样例输入

8
1 4 -3 8 -9 2 -2 1
4
1 5
2 8
3 6
3 3

样例输出

10
9
8
-3

说明

四组查询的答案分别对应为：[1 4 -3 8],[4 -3 8],[8],[-3][1 4 -3 8],[4 -3 8],[8],[-3]。

这道题对原数组做出了一定限制，需要改变遍历原数组的终止位置；

#include<iostream>
using namespace std;
int a[200000];
int main(){
int n=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int m=0;
cin>>m;
while(m–){
int l=1,r;
cin>>l>>r;
int ans=a[l];
int dp=0;
for(int i=l;i<=r;i++){
dp=max(dp+a[i],a[i]);
ans=max(ans,dp);
}
cout<<ans<<endl;

}

return 0;
}

好了接下来来看一道进阶版的题目： 基德的冒险之旅

由于题目过长就简要说明一下：给你一段数组，你要求两端子数组，这两段子数组之间最少要隔k个元素，问两段子数组和最大为多少？

好了来看看与上面题的区别，上面的题你只需要求一段最大的就行了，但这道题你要求两段和最大，

一步一步来，上面的题我用到了dp数组表示以某个元素结尾的最大子数组和，如果这道题dp数组的状态不变的话，我可以从头开始枚举，求出以当前位置结束的最大子数组和，再在后面隔k个位置，去找一个最大子数组和，这么求无疑是复杂的，来看看这两个子数组都有哪些特点：第一个数组开头是固定的，后一个数组结尾是固定的，同时前一个数组还有约束，必须是以当前位置结束的，明显不合适

因此引入了新的状态dp[i]表示前i个元素最大数组和，而第二段数组要找从末尾开始的最大子数组和，只是在求从后到前的情况，那么我把数组反转一下不久和第一段一样了吗？

理一下思路，先从开头到结尾求出来dp1[i]表示所有位置的前i个位置的最大元素和，之后反转原数组，再来从开头到结尾求出来dp2[i]表示所有位置的前i个位置的最大元素和，这时候便是从后往前遍历的（要注意下标问题）

之后遍历每个位置求出在所有情况下的最大值，看前i个元素的最大和加上隔k个元素后从后往前的最大值

int temp=dppre[i]+dphre[n-i-k];这是转换后的两个子数组和

ans=max(ans,temp);

这里遍历每个位置是一定能遍历所有可能的情况，因为对于答案前后数组，前数组一定是某个位置之前的最大子数组和，后数组一定是从某个位置之后的最大子数组和，可以用反证法证明：如果不是那么结果将更大，注意这里的重点在某个位置，当这个位置固定时，前后一定要选最大的。而遍历呢就是在找这个位置。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200001];
int dppre[200001],dphre[200001];
signed main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dppre[0]=0;
for(int i=1;i<=n;i++){
dppre[i]=max(dppre[i-1]+a[i],a[i]);
}
reverse(a+1,a+n+1);
dphre[0]=0;
for(int i=1;i<=n;i++){
dphre[i]=max(dphre[i-1]+a[i],a[i]);
}
for(int i=2;i<=n;i++){
dppre[i]=max(dppre[i],dppre[i-1]);
dphre[i]=max(dphre[i],dphre[i-1]);
}
int ans=-1000000;
for(int i=1;i<=n-k-1;i++){
int temp=dppre[i]+dphre[n-i-k];
ans=max(ans,temp);
}
cout<<ans;

return 0;
}

上面还都是一维动态规划，接下来来到进阶二维状态的题

可删除元素的最大子段和

问题描述

有一个大小为 nn 的整数数组 arrarr ，你可以选择该数组的任意一个非空子数组，并最多删去其中任意 kk 个元素，删除元素后子数组不能为空，然后求出其删除元素后的该子数组的剩余元素和。

请你求出以上操作所能得到的最大元素和。

输入格式

输入格式有 22 行。

第一行为两个整数 n,kn,k ，表示数组的长度为 nn ，最多可以删除一个非空子数组中的 kk 个元素。

第二行为 nn 个整数，表示数组的 nn 个元素，两个元素之间由空格隔开。

注意第二行中的输入数据中可能包含负数。

输出格式

输出一个整数，表示所能得到的最大元素和。

样例输入

5 2
3 -2 -4 0 8

样例输出

11

说明

对于样例来说，选择所有元素，再删除 arr[1]arr[1] 与 arr[2]arr[2] ，就可以得到最大的元素和。

评测数据规模

对于所有评测数据，1≤n≤1000001≤n≤100000，0≤k≤1000≤k≤100 ，−10000≤arr[i]≤10000−10000≤arr[i]≤10000 。

对于最后结果：最大元素可能是删过元素的一段子数组，也可能是没删过的，一次对于dp数组我要用二维表示两个状态：dp[i][j]：第i个元素结尾（可能被删了），恰好用了j次删除之后的最大值（有点像背包dp一定要恰好用了这j次删除，否则就是不合法的）

从删除次数和第i个元素入手，dp[i][j]是以第i个元素结尾（可能被删了），恰好用了j次删除之后所有子数组和的最大值，那么对于这些子数组和又可以看为包不包括第i个元素，如果包括，k次删除机会就要用的前i-1个元素上，去得到的前i-1个子数组的最大值：dp[i][j-1]. + a[i]，如果删了第i个元素，那么就要给前i-1个元素用到k-1次机会，得到:dp[i-1][j-1]; 

所以dp[i][j]=max(dp[i-1][j-1],a[i]+dp[i-1][j-1]);

注意边界条件的处理

dp[0][0]=0;

for(int j=1;j<=k;j++){ dp[0][j]=inf; } //切0刀的情况单独考虑

for(int i=1;i<=n;i++){ dp[i][0]=max(dp[i-1][0]+a[i],a[i]); }

#include <iostream>
using namespace std;
#define inf -1000000000000ll
#define int long long
int a[100001];

//dp[i][j] 以第i个元素结尾，用了k次机会的最大子数组和
//dp[i][j]=dp[i-1][j]+a[i],dp[i-1][j-1];
int dp[100001][110];
signed main()
{ int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dp[0][0]=0;
for(int j=1;j<=k;j++){
dp[0][j]=inf;
}
//切0刀的情况单独考虑
for(int i=1;i<=n;i++){
dp[i][0]=max(dp[i-1][0]+a[i],a[i]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
dp[i][j]=max(dp[i-1][j]+a[i],dp[i-1][j-1]);
}
}
int ans=inf;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
ans=max(ans,dp[i][j]);
}
}
cout<<ans;

return 0;
}