输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。
输入格式 第一行输入两个整数n,m。
第二行输入n个数，代表长度为n的整数序列。
同一行数之间用空格隔开。
输出格式 输出一个整数，代表该序列的最大子序和。
数据范围 1≤n,m≤3000001≤n,m≤300000 样例 输入样例： 6 4 1 -3 5 1 -2 3 输出样例： 7
原问题可以转化为找到两个位置x,y；使得s[y]-s[y]最大而且y-x<m; 首先我们需要找到一个右端点，然后问题就变成了去寻找一个左端点。然后左端点的范围为[i-m,i-1]并且s[j]最小。 假设k<j<i,并且s[k]>=s[j],k永远不会成为最优的选择， 1；首先判断对头是否超出M,超出就出队； 2:对头就是右端点此时就是最优的选择 3：不断删除队尾元素，直到小于s[i],然后把i最为一个新的元素加入队列。
#include<iostream> using namespace std; const int N=300000; int a[N],sum[N],q[N]; int INF = 0x3f3f3f3f; int ans=-INF; int main() {ios::sync_with_stdio(false); int n; int m; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; sum[i]=sum[i-1]+a[i]; } int l=1,r=1; q[1]=0; for(int i=1;i<=n;i++){ while(l<=r&&q[l]<i-m)l++;//距离大于M之后，会进行右移 ans=max(ans,sum[i]-sum[q[l]]); while(l<=r&&sum[q[r]]>=sum[i])//判断队尾元素与当前元素的值大小 r--; q[++r]=i;} cout<<ans; return 0; }