#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = (ll)4e18;
const int maxn = 300000 + 5;
int n, k;
ll a[maxn], sum[maxn];
ll dp[maxn], newdp[maxn], best[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i-1] + a[i];
}
int neg = 0, pos = 0;
for (int i = 1; i <= n; i++){
if (a[i] < 0) neg++;
else pos++;
}
if (pos == n) { cout << sum[n]; return 0; }
if (neg == n) { cout << 0; return 0; }
// K = 1 → bài max subarray
if (k == 1) {
ll ans = -INF, mn = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, sum[i] - mn);
mn = min(mn, sum[i]);
}
cout << ans;
return 0;
}
// DP cho K > 1
for (int i = 0; i <= n; i++) dp[i] = -INF;
dp[0] = 0;
ll ans = 0;
for (int j = 1; j <= k; j++) {
best[0] = dp[0] - sum[0];
for (int i = 1; i <= n; i++)
best[i] = max(best[i-1], dp[i] - sum[i]);
newdp[0] = 0; // đoạn có thể rỗng
for (int i = 1; i <= n; i++) {
newdp[i] = max(newdp[i-1], best[i-1] + sum[i]);
if (j == k) ans = max(ans, newdp[i]);
}
// chuyển sang vòng kế tiếp
for (int i = 0; i <= n; i++)
dp[i] = newdp[i];
}
cout << ans;
}
