翰翰18岁生日的时候，达达给她看了一个神奇的序列 A1,A2,…,AN。

她被允许从中选择不超过 M 个连续的部分作为自己的生日礼物。

翰翰想要知道选择元素之和的最大值。

你能帮助她吗？

输入格式
第一行包含两个整数N,M。

第二行包含N个整数A1~AN。

输出格式
输出一个整数，表示答案。

数据范围
1≤N,M≤$10^5$,
|Ai|≤$10^4$
输入样例：

5 2 
2 -3 2 -1 2

输出样例：

5

问题转化

首先，我们要使$m$段的和尽量大，首先需要选$m$段，并使得$m$段尽量都为整数。如果整数段数$cnt≤m$的话，那么我们全部选上即可，而如果$cnt>m$的话，那么我们则需要删除部分段，而对于删除我们则有下面两个操作可选：

设$k=cnt-m$

而现在我们的问题可以转化为，使我们删除的$k$段尽量地小。

1.删除$1$段整数

2.合并$j$段整数与$j-1$段负数

而对于操作一相当于减去那一段整数的值，而对于操作而相当于减去

而对于操作一来说相当于减去$a_i$，对于操作二来说相当于减去$|a_i|$。

且我们选择的两段肯定不相连（如果选了两端相连的相当于选一段正一段负，一定不会是答案）。

而到此这个问题可以转化为P3620 【[APIO/CTSC 2007]数据备份】

我们就可以通过数据备份这道题的做法去处理这个子问题。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;


typedef pair<int,int> PII;
const int N = 100010;

int n,m,a[N],l[N],r[N];
bool st[N];
priority_queue<PII,vector<PII> ,greater<PII> > heap;

void del(int x){
    r[l[x]] = r[x];
    l[r[x]] = l[x];
    st[x] = true;
}

int main(){
    scanf("%d%d",&n,&m);
    int ans = 0,cnt = 0;
    int k = 1;
    for (int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        if ((long long)a[k] * x < 0) a[ ++ k] = x;
        else a[k] += x;
    }
    n = k;
    for (int i = 1; i <= n; i++){
        if (a[i] > 0){
            ans += a[i];
            cnt++;
        }
        l[i] = i - 1;
        r[i] = i + 1;
        heap.push({abs(a[i]),i});
    }
    while (cnt > m){
        while(st[heap.top().second])heap.pop();
        PII v = heap.top();
        heap.pop();
        if (l[v.second] != 0 && r[v.second] <= n || a[v.second] > 0){
            ans -= v.first;
            cnt--;
            int left = l[v.second], right = r[v.second];
            a[v.second] += a[left] + a[right];

            heap.push({abs(a[v.second]), v.second});
            del(left);
            del(right);
        }
    }
    cout << ans;
    return 0;
}