算法竞赛进阶指南 P53[[算法笔记/数据结构/单调队列]]求最大子序和
P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
1234567891011
long long int ans=1; ans=ans<<63;//ans=-9223372036854775808 int l=1,r=1; q[1]=0; for (int i=1;i<=n;i++){ while (l<=r&&q[l]<i-t)l++;//t为最大子序列长度,若题目没有要求即t==n(序列长度),不可省略。 ans=max(ans,sum[i]-sum[q[l]]); //sum[i]是前缀和 while (l<=r&&sum[q[r]]>=sum[i])r--; q[++r]=i; } cout<<ans;
最大子矩阵和 求最大子矩阵和,思路:将矩阵压缩为一维线性关系,问题变为求最大子段和 P1719 最大加权矩形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
#include<iostream> #include <cstring> #include <cmath> using namespace std; int b[130],a[130]; int sum[130][130]; int main () { int n; cin>>n; memset(a,0,sizeof (a)); //矩阵压缩。 for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ cin>>sum[i][j]; sum[i][j]=sum[i][j]+sum[i-1][j]; } } //转化为求一维的最大子段和 int MAX=-1; int ans=1; int l=1,r=1; int q[150]; MAX=MAX<<31; for (int i=0;i<n;i++){ for (int j=i+1;j<=n;j++){ //求子矩阵的压缩:1行,1-2行,1-3行,2行,2-3行,3.。。 memset(a,0,sizeof (a)); memset(b,0,sizeof (b)); for (int k=1;k<=n;k++){ b[k]=sum[j][k]-sum[i][k]; a[k]=a[k-1]+b[k]; } //求一维的最大子段和 ans=ans<<31;//ans=-9223372036854775808 q[1]=0; for (int t=1;t<=n;t++){ while (l<=r&&q[l]<t-n)l++; ans = max(ans,a[t]-a[q[l]]); while (l<=r&&a[q[r]]>=a[t])r--; q[++r]=t; } MAX=max(MAX,ans); } } cout<<MAX<<endl; return 0; }