本文主要是介绍HDU Max Sum of Max-K-sub-sequence(单调队列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Max Sum of Max-K-sub-sequence
题目链接：Click Here~
题目分析：
题意要求给出N给数的序列，要求你求出其在满足连续子串长度不超过k的最大和。
思路分析：
我们以前都做过，是同一个作者出的题,叫MAX Sum和Max Sum Plus其实这两道题的思想都是差不多的，只是到了MAX SUM PLUS PLUS 之后解题思路就要发生本质上的变化了。扯远了。说回这道题吧，显然很容易想到的算法是N*K的暴力遍历。但这个是明显超时的节奏。所以，要另寻他法。
经过思考之后，我们可以很容易的想到运用前缀和思想。但是题目要求的是K个数，这就是本题的一个卡，我们要如何去突破呢？在经过思考我们有可以在进一步的发现前缀和的特点。例如，6 5 7 1 3 8如果，我们假定最后的结果是以8那个数结尾的，那么如何找到最大的k个连续和呢？显然，只要我们找到了前面最小的（8 - min），则结果一定会最大。但是这个前面的数不能和8的position超过K位.则这个数就是我们要求的答案了。
算法实现：
既然知道了实现思路，那么我们要如何去快速的找到那个在当前值前面不超过K个数的最小值呢？
经过思考，我们可以发现我们只要运用一个单调队列就可以达到这个要求了。
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
using namespace std;const int N = 1e5 + 10;
int sum[2*N],a[2*N],num[2*N];
int main()
{int T,n,k;scanf("%d",&T);while(T--){sum[0] = 0;scanf("%d%d",&n,&k);for(int i = 1;i <= n;++i){scanf("%d",&a[i]);sum[i] = sum[i-1] + a[i];a[i+n] = a[i];}for(int i = n+1;i <= n+k;++i)sum[i] = sum[i-1] + a[i];int rear = 0,front = 0;int st = 1,ed = 1,maxv = -1e10;for(int i = 1;i <= n+k;++i){while(front < rear&&sum[num[rear-1]] > sum[i-1]) rear--; //保持队列的单调递增/* 当调用while时我们可以知道此时是出现了负数。我们知道当sum[num[rear-1]] > sum[i-1]成立时，此时队列中的元素（sum[num[rear-1]] > sum[i-1]）必须出列。因为，后面的数减去sum[num[rear-1]]中的数，一定比减去sum[i-1]的值小。所以我们就让其出列,从而提高代码的效率。 */ num[rear++] = i - 1; while(front < rear&&i - num[front] > k) front++; //使结果至多k个数if(sum[i] - sum[num[front]] > maxv){maxv = sum[i] - sum[num[front]];st = num[front]+1;ed = i;}}if(st > n) st -= n;if(ed > n) ed -= n;printf("%d %d %d\n",maxv,st,ed);}return 0;
}
这篇关于HDU Max Sum of Max-K-sub-sequence(单调队列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
