输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。
例如 1，-3,5,1，-2,3
当m=4时，S=5+1-2+3=7
当m=2或m=3时，S=5+1=6
6 4
1 -3 5 1 -2 3
7
思路：单调队列模板题，维护m个数以内的单调递增前缀和，dp[i]=sum[i]-min（sum[j]）（j<=i&&j>i-m）可以直接记录ans，不用开dp数组。
#include<iostream> #include<cstring> #include<cstring> #include<cstdio> #include<cmath> #include<vector> #include<queue> #include<map> #include<algorithm> #define REP(i, a, b) for(int i = (a); i <= (b); ++ i) #define REP(j, a, b) for(int j = (a); j <= (b); ++ j) #define PER(i, a, b) for(int i = (a); i >= (b); -- i) using namespace std; const int maxn = 3e5+10; template <class T> inline void rd(T &ret){ char c; ret = 0; while ((c = getchar()) < ‘0‘ || c > ‘9‘); while (c >= ‘0‘ && c <= ‘9‘){ ret = ret * 10 + (c - ‘0‘), c = getchar(); } } int n,m,ans; int p[maxn],s[maxn],que[maxn]; int main() { int h=1,t=1; rd(n),rd(m); REP(i, 1, n){ cin>>p[i]; s[i]=s[i-1]+p[i]; } REP(i, 1, n){ while(i-que[h]>m)h++; ans=max(ans,s[i]-s[que[h]]); while(h<=t&&s[que[t]]>s[i])t--; que[++t]=i; } cout<<ans<<endl; }
原文：https://www.cnblogs.com/czy-power/p/10363272.html