#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, k;
long long a[N];
long long dp[N][N][2];

void sol1() {
	long long prefix[n+1];
	prefix[0] = 0;
	for(int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + a[i];
	long long rez = -1e18;
	for(int i = 1; i <= n-1; i++) rez = max(rez, abs(prefix[n] - 2 * prefix[i]));
	cout << rez;
}

long long solve() {
	for(int i = 0; i <= n; i++) for(int j = 0; j <= k; j++) dp[i][j][0] = dp[i][j][1] = -1e18;
	for(int i = 0; i <= n; i++) dp[i][0][0] = 0;
	for(int i = 0; i <= k; i++) dp[0][i][0] = 0;
	for(int i = 1; i <= n; i++) dp[i][1][0] = -a[i];
	for(int i = 2; i <= n; i++) {
		for(int j = 1; j <= min(n, k); j++) {
			dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][0]);
			dp[i][j][0] = max(dp[i][j][0], dp[i-1][j-1][0] - a[i]);
			dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][1]);
			dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-1][1] + a[i]);
			dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][0]);
			if(j > 1) dp[i][j][1] = max(dp[i][j][1], dp[i-1][j-1][0] + a[i]);
		}
	}
	return dp[n][k][1];
}

void sol2() {
	long long rez = -1e18;
	rez = max(rez, solve());
	for(int l = 1, r = n; l < r; l++, r--) swap(a[l], a[r]);
	rez = max(rez, solve());
	cout << rez;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    if(n == k) sol1();
    else sol2();
    return 0;
}