最近在水简单DP题，遇到了两道层层递进的DP题，于是记录一下
一、最大子段和
题意：
给出一个长度为n(n<=1e5)的序列，求连续子段的最大值
比如说2 3 -4 5 的最大值是6
而 2 3 -6 7 的最大值为7
样例输入
6
5 4 3 -15 -12 13
样例输出
13
思路一（前缀和）
因为有负数，所以前缀和的值并非单调递增的
而最大字段和只可能出现在任意两个底谷和顶峰之间
图中红色为最大子段和可能出现的地方
所以正序搜出前缀和最小值，倒序搜出最大值，对每个点获得其左边最小的前缀和，右边最大的前缀和，相减即可得到最大子段和。
代码如下：
#include<queue> #include<string> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define lson root<<1 #define rson root<<1|1 using namespace std; long long sum[100010],a[100010],n,max1[100010],min1[100010]; int main() { for(int i=0;i<=100001;i++) { sum[i]=-99999999999; } scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } long long tmpx=-999999999999,tmpn=999999999999; for(int i=0;i<=n;i++) { tmpn=min(tmpn,sum[i]); min1[i]=tmpn; } for(int i=n;i>=0;i--) { tmpx=max(tmpx,sum[i]); max1[i]=tmpx; } long long ans=-999999999999; for(int i=1;i<=n;i++) { ans=max(ans,max1[i]-min1[i-1]); } printf("%lld ",ans); }
思路二（DP）
设f[i]为到i为止以i为终点的最大子段和
则只有两种情况，要么承接以上一个数为终点的子段，要么自己新开一段，既作为开始的起点又作为结束的终点
那么怎么选择呢？这转移方程显然非常好得到：
f[i]=max{f[i-1]+a[i],a[i]}
于是代码如下：
#include<queue> #include<string> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define lson root<<1 #define rson root<<1|1 using namespace std; long long f[100010],a[100010],n; int main() { f[0]=-99999999999; scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(int i=1;i<=n;i++) { f[i]=max(f[i-1]+a[i],a[i]); } long long ans=-99999999999; for(int i=1;i<=n;i++) { ans=max(ans,f[i]); } printf("%lld ",ans); }
二、最大子矩阵
题意：
给出一个n*m的矩阵(n,m<=200)，在矩阵中选出一个子矩阵，使子矩阵的和最大。
样例输入：
4 4
-1 -1 -1 -1
-1 1 1 -1
-1 1 1 -1
-1 -1 -1 -1
样例输出：
4
思路一（n^4暴力）
就是最简单的暴力，统计二维前缀和，枚举左上节点和右下节点，用容斥来算出这个矩阵的和，记录取最大值。
代码懒得打了，反正理论会T。
思路二（n^3降维后跑最大子段和）
枚举一维的所有宽度，将i-j的宽度压缩到一行
对该行跑一遍最大子段和，统计答案
代码写了两种，一种比较好理解但是容易MLE
另一种内存复杂度更优秀一点
第一种：
#include<queue> #include<string> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define lson root<<1 #define rson root<<1|1 using namespace std; long long n,m,map[233][233],sum[233][233][233],f[233][233][233],ans=-999999999999; int main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%lld",&map[i][j]); } } for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { for(int k=1;k<=m;k++) { sum[i][j][k]=sum[i][j-1][k]+map[j][k]; } } } for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { for(int k=1;k<=m;k++) { f[i][j][k]=max(f[i][j][k-1]+sum[i][j][k],sum[i][j][k]); ans=max(ans,f[i][j][k]); } } } printf("%lld ",ans); }
第二种：
#include<queue> #include<string> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define lson root<<1 #define rson root<<1|1 using namespace std; long long n,m,ans=-99999999999; long long sum[517][517],map[517][517],f[517]; int main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%lld",&map[i][j]); } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { sum[i][j]=sum[i-1][j]+map[i][j]; } } for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { f[0]=0ll; for(int k=1;k<=m;k++) { f[k]=max(f[k-1]+sum[j][k]-sum[i-1][k],sum[j][k]-sum[i-1][k]); ans=max(ans,f[k]); } } } printf("%lld ",max(ans,0ll)); }