输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。
输入格式
第一行输入两个整数n,m。
第二行输入n个数，代表长度为n的整数序列。
同一行数之间用空格隔开。
输出格式
输出一个整数，代表该序列的最大子序和。
数据范围
1≤n,m≤3000001≤n,m≤300000
输入样例：
6 4 1 -3 5 1 -2 3输出样例：
7求不超过 m 的最大字段和，考虑前缀和， k = sum[i] - sum[j-1]
不断右移右端点，维护离右端点 i 距离不超过 m的最小前缀和 SUM(min) ，则sum[i] - SUM(min)是当前区间 最大字段和。
所以维护一个单调递增队列就行了。
AC Code：
#include<iostream> #include<iomanip> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<string> #include<algorithm> #include<vector> #include<map> #include<stack> #include<queue> #include<deque> #include<set> #include<bitset> #include<cctype> #define LL long long #define maxn (LL)1e6 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define pb push_back #define re register LL const double eps = 0.0000001; using namespace std; typedef pair<LL,LL> pii; inline int sgn(double x) { return (x > eps) - (x < -eps); } int ans[maxn],rise[maxn],sum[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE //freopen("input.txt","r",stdin); #endif // ONLINE_JUDGE int n,m; cin>>n>>m; for(re i = 1;i<=n;++i) { cin>>ans[i]; sum[i] = sum[i-1] + ans[i];//前缀 } int head = 1,tail =1; rise[tail] = 1; int MAX = sum[1]; for(re i = 2;i<=n;++i) { MAX = max(MAX,sum[i] - sum[rise[head]]);//取最优 while(head<=tail&&sum[i]<=sum[rise[tail]]) tail--;//维护单调递增队列，头部最小 tail ++; rise[tail] = i; while(rise[head]<=i - m&&head<=tail) head++;//是否超过范围m } cout<<MAX<<endl; }
