题意： 给出一个长度为n的数列，要求从中取出不超过m段连续的数，使其和最大。
n<=100000

解题方法：
这题可以把一段同号的数并成一个数，那么就变成了一个正负交替的序列，然后把头尾的负数去掉。
有一种想法就是把所有的正值都加起来，然后把所有数的绝对值加进优先队列，每次去一个最小的出来然后减掉，最后的即为答案。
为什么是正确的呢？因为如果减去的值在原数列中为正则相当于不要这个数，否则就相当于选了这个负数然后把两边的正值合并起来。
但有一个问题，就是若选了一个数那么其两边的数就必定不能被选，那么就转换成了数据备份了。
题解参考的hzwer大牛的，orz

//bzoj 1150
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x7fffffff;
const int maxn = 100010;
typedef long long LL;
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
inline LL llread(){
    char ch=getchar();
    LL f=1,x=0;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
struct node{
    int pos, v;
    node(){}
    node(int pos, int v) : pos(pos), v(v) {}
    bool operator < (const node &rhs) const{
        return v > rhs.v;
    }
};
priority_queue <node> que;
int n, m, a[maxn], b[maxn], L[maxn], R[maxn], vis[maxn];

int main(){
    n = read(); m = read();
    for(int i = 1; i <= n; i++) b[i] = read();
    int n1 = 1;
    a[1] = b[1];
    for(int i = 2; i <= n; i++){
        if(a[n1] <= 0 && b[i] <= 0) a[n1] += b[i];
        else if(a[n1] >= 0 && b[i] >= 0) a[n1] += b[i];
        else a[++n1] = b[i];
    }
    if(a[n1] <= 0) n1--;
    if(a[1] <= 0){
        for(int i = 1; i < n1; i++){
            a[i] = a[i+1];
        }
        n1--;
    }
    n = n1;
    int cnt = 0, ans = 0;
    for(int i = 1; i <= n; i++){
        if(a[i] > 0){
            cnt++;
            ans += a[i];
        }
        que.push(node(i, abs(a[i])));
        a[i] = abs(a[i]);
        L[i] = i - 1;
        R[i] = i + 1;
    }
    R[n] = L[1] = 0;
    if(cnt <= m){
        printf("%d\n", ans);
        return 0;
    }
    m = cnt - m;
    for(int i = 1; i <= m; i++){
        node now = que.top(); que.pop();
        while(vis[now.pos] && !que.empty()) {now = que.top(); que.pop();}
        if(vis[now.pos]) break;
        ans -= now.v;
        if(que.empty()) break;
        int x = now.pos;
        if(!R[x]){
            vis[x] = 1; vis[L[x]] = 1;
            R[L[L[x]]] = 0;
        }
        else if(!L[x]){
            vis[x] = 1; vis[R[x]] = 1;
            L[R[R[x]]] = 0;
        }
        else{
            node nxt;
            vis[L[x]] = vis[R[x]] = 1;
            nxt.v = a[x] = a[R[x]] + a[L[x]] - a[x];
            nxt.pos = x;
            que.push(nxt);
            if(R[R[x]]) L[R[R[x]]] = x;
            if(L[L[x]]) R[L[L[x]]] = x;
            L[x] = L[L[x]];
            R[x] = R[R[x]];
        }
    }
    printf("%d\n", ans);
    return 0;
}