Max Sum of Max-K-sub-sequenceTime Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
hdu3415

Description
Given a circle sequence A,A,A……A[n]. Circle sequence means the left neighbour of A is A[n] , and the right neighbour of A[n] is A.
Now your job is to calculate the max sum of a Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty sub-sequence which length not exceed K.

Input
The first line of the input contains an integer T(1<=T<=100) which means the number of test cases. Then T lines follow, each line starts with two integers N , K(1<=N<=100000 , 1<=K<=N), then N integers followed(all the integers are between -1000 and 1000). Output For each test case, you should output a line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the minimum start position, if still more than one , output the minimum length of them. Sample Input 4 6 3 6 -1 2 -6 5 -5 6 4 6 -1 2 -6 5 -5 6 3 -1 2 -6 5 -5 6 6 6 -1 -1 -1 -1 -1 -1 Sample Output 7 1 3 7 1 3 7 6 2 -1 1 1

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 ``` ```#include #include #include #include #include   using namespace std;   #define N 100010 #define INF 1<<31-1; int a[2*N], sum[2*N]; int num[2*N];   int main(){ int n, k; int beg, end; int i, j, h, t; int maxn; int cnt; scanf("%d", &cnt); while(cnt --){ scanf("%d %d", &n, &k); sum = 0; for(i = 1; i <= n; i ++){ scanf("%d", &a[i]); sum[i] = sum[i-1] + a[i]; } for(i = n+1; i <= 2*n; i ++){ sum[i] = sum[i-1] + a[i-n]; // } maxn = -INF; beg = 0; end = 0; h = 0; t = 0; for(i = 0; i < n + k; i ++){ while(h < t && sum[num[t-1]] > sum[i]) t--; num[t++] = i;//sum[num[i]]sum,sum[i+1]-sum[num[]] while(h < t && i+1 - num[h] > k) h ++;//m if(sum[i+1] - sum[num[h]] > maxn){ maxn = sum[i+1] - sum[num[h]];//maxs beg = num[h] + 1; end = i + 1; } } if(beg > n) beg -= n; if(end > n) end -= n; cout << maxn << " " << beg << " " << end << endl; } return 0; }```