hdu3415MaxSumofMax-K-sub-sequence

 1 /*
 2 *限定长度的循环数据集最大连续子序列和，用队列保存前i个数中小于sum[i]的数。
 3 */
 4 #include 
 5 #include 
 6 using namespace std;
 7 struct min_sum{
 8     int min_index,min_value;
 9     min_sum(){}
10     min_sum(int min_index,int min_value):min_index(min_index),min_value(min_value){}
11 }qv[200010];
12 int num[100010],sum[200010];
13 int main()
14 {
15     int i,n,k,tempx,tempy,tempmin,tempmax,tempsum,T;
16     scanf("%d",&T);
17     while(T--)
18     {
19         scanf("%d%d",&n,&k);
20         sum[0]=0;
21         for(i=1;i<=n;i++)
22         {
23             scanf("%d",&num[i]);
24             sum[i]=sum[i-1]+num[i];
25         }
26         for(i=1;i<=k;i++)
27         {
28             sum[n+i]=sum[n+i-1]+num[i];
29         }
30         tempx=tempy=0;
31         tempsum=-2147483646;
32         tempmin=tempmax=0;
33         qv[tempx++]=min_sum(0,0);
34         for(i=1;i<=n+k;i++)
35         {
36             while(tempyk)
37             {
38                 tempy++;
39             }
40             if(sum[i]-qv[tempy].min_value>tempsum)
41             {
42                 tempsum=sum[i]-qv[tempy].min_value;
43                 tempmin=qv[tempy].min_index+1;
44                 tempmax=i;
45             }
46             while(tempy1].min_value>sum[i])
47             {
48                 tempx--;
49             }
50             qv[tempx++]=min_sum(i,sum[i]);
51         }
52         tempmin-=(tempmin>n?n:0);
53         tempmax-=(tempmax>n?n:0);
54         printf("%d %d %d\n",tempsum,tempmin,tempmax);
55     }
56     return 0;
57 }