题意：求一个环中最大区间和，区间长度 <= n。 用单调队列优化Dp，核心内容是dp[i] = max(sum[j]) - sum[i-1]。

这题最后的输出有很多要求，如果有多个解，输出起始位置最小的；如果还有多个解，输出长度最小的。其实完全不用考虑，因为我遍历的时候就是按起始位置从小到大的，如果一个解和最优解相同，并不更新，记录的就是起始最小的结果。另一个要求亦然。

1 #include 
     
       2 #include 
      
        3 const int N = 100010; 4 const int INF = 1000000000; 5 int a[N],sum[N<<1]; 6 int max[N],dp[N],v[N]; 7 int s,e; 8 int main() 9 {10     int T,n,k,i,Max,x,y;11     scanf("%d",&T);12     while(T--)13     {14         scanf("%d%d",&n,&k);15         for(i = 1; i <= n; i++)16             scanf("%d",&a[i]),17             sum[i] = sum[i-1] + a[i];18         for(i = 1; i < k; i++)19             sum[n+i] = sum[n-1+i] + a[i];20         memset(max,0,sizeof max);21         s = e = 0;22         for(i = 1; i <= k; i++)23         {24             while(s <= e && sum[i] > sum[max[e]])25                 e--;26             max[++e] = i;27         }28         for(i = 1; i <= n; i++)29         {30             while(s <= e && max[s] < i) s++;31             dp[i] = sum[max[s]] - sum[i-1];32             v[i] = max[s];33             while(s <= e && sum[i+k] > sum[max[e]])34                 e--;35             max[++e] = i+k;36         }37         Max = -INF;38         for(i = 1; i <= n; i++)39             if(dp[i] > Max)40                 Max = dp[i],41                 x = i, y = v[i];42         printf("%d %d %d\n",Max,x, y>n ?y%n :y);43     }44     return 0;45 }