$\mathcal{Preface}$

三倍经验：

• #47. K个最大连续子序列和（ksum）
• P6821 [PA2012]Tanie linie
• CF280D k-Maximum Subsequence Sum

$\mathcal{Solution}$

两种理解方法，代码是一样的。

$\mathcal{Solution1}$

• 考虑反悔贪心，每次取最大子段和，然后把该子段取相反数，总是最优的。
• 取了被取相反数的数，相当于撤销原来覆盖这里的子段取这个数，现在的子段也不取这个数。
• 时间复杂度 $\mathcal{O}(kn)$。可以使用线段树维护之，时间复杂度 $\mathcal{O}(k\log n)$。

$\mathcal{Solution2}$

考虑建一个有点权无边权的线性的图，第 $i$ 个权值为 $a_i$。建超级源点 $S$，超级汇点 $T$。

定义 $\text{Add}(u,v,w)$ 为建一条 $u\to v$，容量为 $w$ 的边。

• 则对于 $i\in[1,n]$，$\text{Add}(S,i,1)$ 并 $\text{Add}(i,T,1)$，容量随便写一个 $\geq1$ 的数，因为取的次数下面会控制。
• 对于 $1\in[1,n-1]$，$\text{Add}(i,i+1,1)$，因为每个点只能取一次。

跑最大费用最大流即可。

时间复杂度 $\mathcal{O}(kn^2)$，跑不满。

• 发现复杂度瓶颈在于求 $S\to T$ 的最长路。
• 这个等价于求最大子段和，那么用线段树模拟费用流即可。需要支持区间变为相反数，区间求最大子段和。

时间复杂度 $\mathcal{O}(k\log n)$。

$\mathcal{Code}$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct node {
	int l, r;
	long long v;
	node(int _l, int _r, int _v) :
		l(_l), r(_r), v(_v) {}
	node() {}
	void operator ^= (int x) { if (x) v = -v; }
	bool operator < (const node& x) const { return v < x.v; }
	bool operator > (const node& x) const { return v > x.v; }
} id(0, 0, 0);
struct tree {
	node ls, rs, lm, rm, ans, res;
	int l, r;
	long long sum;
	tree() { ls = rs = lm = rm = ans = res = id, sum = 0; }
	tree(int p, int x) {
		node a(p, p, 0), b(p, p, x);
		ls = rs = ans = max(a, b), lm = rm = res = min(a, b), sum = x;
	}
} sum[N << 2];
int n, q, opt, l, r, k, tag[N << 2], a[N];
inline tree operator + (const tree& L, const tree& R) {
	tree res;
	res.sum = L.sum + R.sum;
	res.ls = max({L.ls, node(0, R.ls.r, L.sum + R.ls.v), node(0, res.l, 0)});
	res.rs = max({R.rs, node(L.rs.l, 0, R.sum + L.rs.v), node(res.r, 0, 0)});
	res.lm = min({L.lm, node(0, R.lm.r, L.sum + R.lm.v), node(0, res.l, 0)});
	res.rm = min({R.rm, node(L.rm.l, 0, R.sum + L.rm.v), node(res.r, 0, 0)});
	res.ans = max({L.ans, R.ans, node(L.rs.l, R.ls.r, L.rs.v + R.ls.v)});
	res.res = min({L.res, R.res, node(L.rm.l, R.lm.r, L.rm.v + R.lm.v)});
	return res;
}
inline void operator ^= (tree& x, int y) {
	if (!y) return;
	swap(x.ans, x.res), swap(x.ls, x.lm), swap(x.rs, x.rm);
	x.ans ^= 1, x.res ^= 1, x.ls ^= 1, x.rs ^= 1, x.lm ^= 1, x.rm ^= 1, x.sum *= -1;
}
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }
inline void push_up(int p) { sum[p] = sum[ls(p)] + sum[rs(p)]; }
inline void push_down(int p) {
	tag[ls(p)] ^= tag[p], sum[ls(p)] ^= tag[p];
	tag[rs(p)] ^= tag[p], sum[rs(p)] ^= tag[p];
	tag[p] = 0;
}
void build(int p, int l, int r) {
	if (l == r) { sum[p] = tree(l, a[l]), sum[p].l = l, sum[p].r = r; return; }
	int mid = (l + r) >> 1;
	build(ls(p), l, mid), build(rs(p), mid + 1, r);
	push_up(p);
}
void modify(int p, int l, int r, int t, int k) {
	if (l == r) { sum[p] = tree(l, k), tag[p] = 0; return; }
	int mid = (l + r) >> 1;
	push_down(p);
	if (t <= mid) modify(ls(p), l, mid, t, k);
	if (t > mid) modify(rs(p), mid + 1, r, t, k);
	push_up(p);
}
void inverse(int p, int l, int r, int nl, int nr) {
	if (nl <= l && r <= nr) { sum[p] ^= 1, tag[p] ^= 1; return; }
	int mid = (l + r) >> 1;
	push_down(p);
	if (nl <= mid) inverse(ls(p), l, mid, nl, nr);
	if (nr > mid) inverse(rs(p), mid + 1, r, nl, nr);
	push_up(p);
}
tree query(int p, int l, int r, int nl, int nr) {
	if (nl <= l && r <= nr) return sum[p];
	tree res;
	int mid = (l + r) >> 1;
	push_down(p);
	if (nl <= mid) res = query(ls(p), l, mid, nl, nr) + res;
	if (nr > mid) res = res + query(rs(p), mid + 1, r, nl, nr);
	return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	build(1, 1, n);
	long long res = 0;
	vector<tree> t;
	while (k --) {
		tree u = query(1, 1, n, 1, n);
		res += u.ans.v;
		if (u.ans.l && u.ans.r) t.push_back(u), inverse(1, 1, n, u.ans.l, u.ans.r);
	}
	cout << res << '\n';
	return 0;
}

using namespace std;
int n,m,a[1001][1001],b[1001],ma=INT_MIN;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=m;i++)
	for(int j=1;j<=n;j++)
	{
		a[i][j]=a[i][j-1]+b[j];
		for(int k=i-1;k<=j-1;k++)
			a[i][j]=max(a[i][j],a[i-1][k]+b[j]);
		ma=max(ma,a[i][j]);
	}
	cout<<ma;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, K = 15;
long long f[N][K][2], n, m, ans, x;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> x;
		for (int j = 1; j <= m; j ++) {
			f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j - 1][1]) + x;
			f[i][j][1] = max(f[i - 1][j][0], f[i - 1][j][1]);
			if (j == m) ans = max(ans, max(f[i][j][0], f[i][j][1]));
		}
	}
	cout << ans << '\n';
	return 0;
}