#include <cstdio>
#include <cstring>

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[2][MAX_N], c[2][MAX_N];

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

int make(int l, int r)
{
	return d[0][l - 1] + s[r] - s[l - 1];
}

void dinamica()
{
	int i, j;

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

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

			dq[++dr] = j;

			c[1][j] = make(dq[st], j);
			d[1][j] = max(d[1][j - 1], c[1][j]);
		}

		memcpy(c[0], c[1], sizeof(c[0]));
		memcpy(d[0], d[1], sizeof(d[0]));
	}
}

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[0][n];

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

	dinamica();

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

	printf("%d\n", (sol < 0) ? 0 : sol);
}