#include<cstdio>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

const int INF = 1000000005;
const int NMAX = 10005;
const int KMAX = 1005;

int N, K, REZ;
int a[NMAX], s[NMAX];
int d[2][NMAX];

void citi()
{
	scanf("%d%d", &N, &K);
	for(int i = 1 ; i <= N ; i++)
	{
		scanf("%d", &a[i]);
		s[i] = s[i - 1] + a[i];
	}
}

void dinamic()
{
	for(int i = 1 ; i <= K ; i++)
	{
		int maxim = -INF, poz = 0;
		for(int j = 1 ; j <= N ; j++)
		{	
			if(d[(i - 1) % 2][j] - s[j] > maxim)
			{
				maxim = d[(i - 1) % 2][j] - s[j];
				poz = j;
			}			
			d[i % 2][j] = max(d[i % 2][j - 1], maxim + s[j]);			
		}
	}
}

void scrie()
{
	printf("%d\n", REZ);
}

int main()
{
	freopen("ferma.in", "r", stdin);
	freopen("ferma.out", "w", stdout);
	citi();
	dinamic();
	REZ = d[K % 2][N];
	copy(s + 1, s + N + 1, d[0] + 1);
	dinamic();
	for(int i = 2 ; i < N ; i++)
		REZ = max(REZ, d[K % 2][i] + s[N] - s[i]);
	scrie();
	return 0;
}