#include <cstdio>

const int MAX_N = 10002;
const int MAX_K = 1002;
const int INF = 0x3f3f3f3f;

int n, k, st, dr;
int a[MAX_N], s[MAX_N], dq[MAX_N];
int d[MAX_K][MAX_N];

inline int max(int a, int b) { return (a > b) ? a : b; }

void dinamica()
{
	int i, j;

	for (i = 1; i <= k; ++i)
	{
		d[i][0] = -INF;
		st = 1, dr = 0;

		for (j = 1; j <= n; ++j)
		{
			while (dr >= st && d[i - 1][j - 1] - s[j - 1] > d[i - 1][dq[dr] - 1] - s[dq[dr] - 1])
				--dr;

			dq[++dr] = j;

			d[i][j] = max(d[i][j - 1], d[i - 1][dq[st] - 1] - s[dq[st] - 1] + s[j]);
		}
	}
}

int main()
{
	int i;
	freopen("ferma.in", "r", stdin);
	freopen("ferma.out", "w", stdout);

	scanf("%d %d", &n, &k);

	for (i = 1; i <= n; s[i] = s[i - 1] + a[i], ++i)
		scanf("%d", &a[i]);

	dinamica();

	int sol = d[k][n];

	for (i = 1; i <= n; ++i)
		d[1][i] = max(s[i], d[1][i - 1]);

	dinamica();

	for (i = 1; i <= n; ++i)
		sol = max(sol, d[k][i] + s[n] - s[i]);

	printf("%d\n", sol);
}