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超过K.则这个数就是我们要求的答案了。
算法实现：
既然知道了实现思路，那么我们要如何去快速的找到那个在当前值前面不超过K个数的最小值呢？
经过思考，我们可以发现我们只要运用一个单调队列就可以达到这个要求了。
#include#include #include #include 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; }