大半个月前做的题，现在才写题解，/qd/qd。
贪心，选出 \(k\) 个不相交子段的和的最大值，其实相当于每次把序列最大子段拎出来，加上去，然后取相反数。
证明的话可以考虑模拟费用流，\(i\le n\)，\(S\to i\) 连边，\(i\to i+1\) 连边，\(i\to T\) 连边，边的流量均为 \(1\)，\(i\to i+1\) 费用为 \(-a_i\)。流 \(S\to i\to j\to T\) 相当于取了 \([i,j-1]\)，于是变成费用流模型。
费用流的时候就是每次贪心取最小的，所以这里贪心取最大的取反即可。
然后就不难线段树维护了。