Solution
可以用WQS二分，但我不会。乱贪虽然可以过，但可惜是假的。还有一个费用流做法。
先建 (n+1) 个节点和一个源点和汇点。源点向所有点连边，所有点向汇点连边。点 (i) 向 (i+1) 连一条费用为 (a_i) 的边，跑最大费用最大流。
每次增广，实际上是选了一段的数。每次增广后，将所有在增广路上的边的边权取反。如果下次增广又增广到了这条边，那么相当于抵消了，就没选，而选了的被分成两段。所以每次增广就选了一段不相交的数。
这个算法慢在每次增广后都要暴力修改边权，所以不能直接费用流。考虑模拟费用流，然后用数据结构进行优化。事实上，我们只需要每次求出全局的最大子段和，然后累加答案，再将这个子段取反，如果最大子段已经为负或已经选了 (k) 段就直接退出。最大子段和还有其所在位置很好维护，关键在于取反。又发现取反只会有两种结果，所以在线段树中预处理每种情况。维护一个取反 tag ，取反就直接交换预处理好的 tr[0][id] 和 tr[1][id]，然后再 update 一下。
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 100007
#define lid id<<1
#define rid id<<1|1
#define ll long long
inline int read(){
int x=0,flag=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-') flag=0;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return flag? x:-x;
}
struct Node{
ll ls,rs,s,ans;
int l,r,ansl,ansr;
}tr[2][N<<2];
int n,K,tag[N<<2];
ll a[N];
void update(int id){
for(int i=0;i<=1;i++){
/* SUM */
tr[i][id].s=(tr[i][lid].s+tr[i][rid].s);
/* LSUM */
if(tr[i][lid].s+tr[i][rid].ls>tr[i][lid].ls)
tr[i][id].ls=tr[i][lid].s+tr[i][rid].ls,tr[i][id].r=tr[i][rid].r;
else tr[i][id].ls=tr[i][lid].ls,tr[i][id].r=tr[i][lid].r;
/* RSUM */
if(tr[i][rid].s+tr[i][lid].rs>tr[i][rid].rs)
tr[i][id].rs=tr[i][rid].s+tr[i][lid].rs,tr[i][id].l=tr[i][lid].l;
else tr[i][id].rs=tr[i][rid].rs,tr[i][id].l=tr[i][rid].l;
/* ANS */
tr[i][id].ans=-(1LL<<60);
if(tr[i][lid].ans>tr[i][id].ans)
tr[i][id].ans=tr[i][lid].ans,tr[i][id].ansl=tr[i][lid].ansl,tr[i][id].ansr=tr[i][lid].ansr;
if(tr[i][rid].ans>tr[i][id].ans)
tr[i][id].ans=tr[i][rid].ans,tr[i][id].ansl=tr[i][rid].ansl,tr[i][id].ansr=tr[i][rid].ansr;
if(tr[i][lid].rs+tr[i][rid].ls>tr[i][id].ans)
tr[i][id].ans=tr[i][lid].rs+tr[i][rid].ls,tr[i][id].ansl=tr[i][lid].l,tr[i][id].ansr=tr[i][rid].r;
}
}
inline void pushup(int id){
swap(tr[0][id],tr[1][id]);
tag[id]^=1;
}
inline void pushdown(int id){
pushup(lid),pushup(rid);
tag[id]=0;
}
int l,r;
void modify(int id,int lf,int rf){
if(l<=lf&&rf<=r) pushup(id);
else{
int mid=(lf+rf)>>1;
if(tag[id]) pushdown(id);
if(l<=mid) modify(lid,lf,mid);
if(r>mid) modify(rid,mid+1,rf);
update(id);
}
}
void build(int id,int lf,int rf){
if(lf==rf){
for(int i=0;i<=1;i++){
tr[i][id].ls=tr[i][id].rs=tr[i][id].s=tr[i][id].ans=a[lf]*(i? -1:1);
tr[i][id].l=tr[i][id].r=tr[i][id].ansl=tr[i][id].ansr=lf;
}
tag[id]=0;
}else{
int mid=(lf+rf)>>1;
build(lid,lf,mid);
build(rid,mid+1,rf);
update(id);
}
}
int main(){
freopen("maxksum.in","r",stdin);
freopen("maxksum.out","w",stdout);
n=read(),K=read();
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
ll ans=0;
while(K--){
ll ret=tr[0][1].ans;
if(ret<=0) break;
ans+=ret;
l=tr[0][1].ansl,r=tr[0][1].ansr;
modify(1,1,n);
}
printf("%lld",ans);
}
/*
7 2
-1 9 -2 6 -8 1 -7
*/