Divide Cake

Problem Statement

今天是小 Z 的生日，同学们为他带来了一块蛋糕。这块蛋糕是一个长方体，被用不同色彩分成了 $n$ 个相同的小块，每小块都有对应的幸运值。

小 Z 作为寿星，自然希望吃到的蛋糕的幸运值总和最大，但小 Z 最多又只能吃 $m(m\le n)$ 小块的蛋糕。

请你帮他从这 $n$ 小块中找出连续的 $k(1 \le k\le m)$ 块蛋糕，使得其上的总幸运值最大。

形式化地，在数列 ${p_n}$ 中，找出一个子段 $[l,r](r-l+1\le m)$，最大化 $\sum\limits_{i=l}^rp_i$。

Input

第一行两个整数 $n,m$。分别代表共有 $n$ 小块蛋糕，小 Z 最多只能吃 $m$ 小块。

第二行 $n$ 个整数，第 $i$ 个整数 $p_i$ 代表第 $i$ 小块蛋糕的幸运值。

Output

仅一行一个整数，即小 Z 能够得到的最大幸运值。

Sample Input

Sample Output

1

9

Sample Input#2

1
2


6 3
1 -2 3 -4 5 -6

Sample Output#2

1

5

Constraints

对于 $20%$ 的数据，有 $1\le n\le100$。
对于 $100%$ 的数据，有 $1\le n\le5\times 10^5$，$|p_i|≤500$。

保证答案的绝对值在 $[0,2^{31}-1]$ 之内。

Solving

维护一个单调队列，其中存储数组的下标。

即不断维护一个最优的前缀和的左端点。

当队列中元素对应的前缀和是递增的时候，对于当前右端点 i，队首元素对应的前缀和是队列中最小的。根据子段和的计算公式 prefix[i] - prefix[l - 1]，要使子段和最大，就需要找到一个合适的左端点 l - 1，使得 prefix[l - 1] 尽可能小。因此，队首元素对应的左端点就是当前情况下的最优左端点，我们可以直接用 prefix[i] - prefix[q.front()] 来计算以 i 为右端点的最大子段和。

由于是res = prefix[i] - prefix[q.front()],所以我们要尽量的使得该区间的最优左端点的前缀和更小,即能保证获得的res最优。

 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


const int N = 5e5+10;
const int M = 0;
int prefix[N]; 
void solve()
{   
    int n,k;
    cin >> n >> k;
    int arr[n+1];
    for(int i=1;i<=n;i++) cin >> arr[i];
    int res = NINF;
    for(int i=1;i<=n;i++)
    {
        prefix[i] = prefix[i-1] + arr[i];
    }
    deque<int> q;//维护可能的最优左端点
    q.push_back(0);//初始化左端点为0！
    for(int i=1;i<=n;i++)
    {
        while(q.front()+k<i) q.pop_front();
        res = max(res,prefix[i]-prefix[q.front()]);
        //使得最优左端点的前缀和尽可能小
        while(!q.empty()&&prefix[q.back()]>=prefix[i]) q.pop_back();
        q.push_back(i);
    }
    cout << res;
}