#include using namespace std; const int N = 300010; const int INF = 0x3f3f3f3f; int n, m; int q[N]; // 单调队列,本质记录的是下标序号,因为只有记录了下标,才能知道是否离i的距离长度超过m了没有。 // 同时,记录了下标的话,想要其它的信息都是可以表示出来的,比如s[q[hh]] int s[N]; // 前缀和 int res = -INF; // 预求最大,先设最小 int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1]; // 前缀和 int hh = 0, tt = 0; // 等价于增加了一个哨兵节点,也就是把下标为0的前缀和s[0]=0加入了滑动窗口中,描述1号节点向前m个节点的前缀和最小值是0 // 枚举右边界 for (int i = 1; i <= n; i++) { // 1、老掉牙的需要去世 while (hh <= tt && q[hh] < i - m) hh++; // 2、此时单调队列中保存就是i以前、长度最长为m的单调上升的一个序列,队列头保存的就是i前面前缀和的最小值 // 此时i还没有进入队列,单调队列其实在枚举数字i的左侧 res = max(res, s[i] - s[q[hh]]); /* 把0,也就是sum(0)塞入队列中(这是给sum(1)用的,因为可能sum(1)-sum(0)就是最大的子序列,不加这个0就没法计算了),最小值为0 */ // 3、i入队列 // 比i老没它小的都去死吧~ while (hh <= tt && s[q[tt]] >= s[i]) tt--; // i入队列,本轮结束 q[++tt] = i; } // 输出结果 cout << res << endl; return 0; }