本题又是一题单调队列题解。

技巧就是需要计算好前n项和Sn = a1 + a2 + ... an

这样方便处理。

记录一条单调队列，其意义是： q(head), q(head+1), ...q(tail)

其中头q(head)代表当前最佳解的起点

这样我们只需要在求某点为结尾的S[i] - S[q(head)就得到当前最佳值。

了解了单调数列，知道其中的记录意义，那么这道题就没有难度了。我也是了解这些信息之后就自己敲出代码的。

不过有些细节没写好也让我WA了几次。

最近少刷水题，而一直都是每天一个新的算法，也学了不少算法了。

#include 
  
   
#include 
   
     const int MAX_N = 100001; int N, K; int arr[MAX_N]; int S[MAX_N<<1]; int qu[MAX_N<<1]; int val, sta, end; void getMaxK() { int tail = 0, head = 0; qu[0] = 0; //记录S数组的下标 int len = N+K; val = INT_MIN; for (int i = 1; i < len; i++) { while (tail >= head && S[i-1] <= S[qu[tail]]) tail--; while (tail >= head && qu[head] < i - K) head++;//不能漏了tail>=head qu[++tail] = i-1;//这句可以放前一句前面，那么就可以不用tail>=head判断了 int sum = S[i] - S[qu[head]]; if (sum > val || sum == val && qu[head]+1==sta && i-qu[head]
    
      N) end = end % N; printf("%d %d %d\n", val, sta, end); } return 0; }