Description：

在一个序列中选不超过 $M$ 个部分使得他们和最大。

$1\le n \le 10^5$

Solution：

把所有符号相同的部分合在一起，舍弃两端的负段，并把剩下的块和的绝对值放入小根堆中，先把 $ans$ 设为所有正块的和，每次从堆顶取出一个，并把 $ans$ 减这块的和，如果它原来为正，那么相当于不选这一块，如果原来为负，那么相当于把左右连起来，都会使块数减少。

但是这样做有一个问题，如果它和它两边都被取出来了，那么就起不到应有的效果了，所以必须保证取完这个之后两边的不能取了，或者这块也不取了，于是把他和左右合在一起放入堆中，把堆中原来它左右的删掉即可，这个可以用双向链表来做。

注意最两边为负的不能要，要提前消掉，如果在中途产生了，也要一起删掉而不是和后面的合并。合并后的块的权值为 $val[pre]+val[nxt]-val[pos]$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

    register int res = 0;

    register char c = getchar();

    int f = 1;

    while(!isdigit(c))

    {

        if(c == '-')f = -1;

        c = getchar();

    }

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res * f;

}

int n,m;

#define MAXN 100010

int a[MAXN];

int block[MAXN],blocks = 0;

int lef[MAXN],rig[MAXN];

#define fi first

#define se second

bool tag[MAXN];

priority_queue< pair<int,int> > q;

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;++i)a[i] = read();

    int w = 1;while(w <= n && a[w] <= 0)++w;

    while(a[n] <= 0)--n;

    int sum = 0;

    for(;w <= n;++w)

    {

    	if((a[w - 1] <= 0 && a[w] <= 0) || (a[w - 1] > 0 && a[w] > 0))block[blocks] += a[w];

    	else block[++blocks] = a[w];

    }

    sum = 0;

    int tot = 0;

    for(int i = 1;i <= blocks;++i)

    {

        if(block[i] > 0)

        {

            sum += block[i];

            ++tot;

        }

    }

    if(tot <= m)

    {

        printf("%d\n",sum);

        return 0;

    }

    for(int i = 1;i <= blocks;++i)

    {

        lef[i] = i - 1;rig[i] = i + 1;

        q.push(make_pair(-abs(block[i]),i));

    }

    while(tot > m)

    {

        pair<int,int> k = q.top();q.pop();

        if(tag[k.se])continue;

        --tot;

        int val = -k.fi,pos = k.se;

        sum -= val;

        if(rig[pos] == blocks + 1)

        {

        	tag[pos] = tag[lef[pos]] = true;

            int r = lef[lef[pos]];

            rig[r] = blocks + 1;

            continue;

        }

        if(lef[pos] == 0)

        {

        	tag[pos] = tag[rig[pos]] = true;

            int l = rig[rig[pos]];

            lef[l] = 0;

            continue;

        }

        val = abs(block[lef[k.se]]) + abs(block[rig[k.se]]) - val;

        block[k.se] = val;

        tag[lef[k.se]] = tag[rig[k.se]] = true;

        rig[lef[lef[k.se]]] = k.se;lef[k.se] = lef[lef[k.se]];

		lef[rig[rig[k.se]]] = k.se;rig[k.se] = rig[rig[k.se]];

        q.push(make_pair(-abs(val),k.se));

    }

    cout << sum << endl;

    return 0;

}