#include<stdio.h>
int n,k,i,j,c,s[10001],oo,d[1001][10001],sol,best;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("ferma.in","r",stdin);
	freopen("ferma.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&s[i]);
		s[i]+=s[i-1];
	}
}
void solve()
{
	oo=2000000000;
	for(c=1;c<=k;c++)
	{
		d[c][c]=s[c];best=0;
		for(i=c+1;i<=n;i++)
		{
			best=best>d[c-1][i]-s[i]?best:d[c-1][i]-s[i];
			d[c][i]=d[c][i-1]>best+s[i]?d[c][i-1]:best+s[i];
		}
	}
	sol=d[k][n];
	d[1][1]=s[1];
	for(i=2;i<=n;i++)d[1][i]=s[i]>d[1][i-1]?s[i]:d[1][i-1];
	best=0;
	for(c=2;c<=k;c++)
	{
		best=-oo;
		for(i=c;i<=n;i++)
		{
			best=best>d[c-1][i]-s[i]?best:d[c-1][i]-s[i];
			d[c][i]=d[c][i-1]>best+s[i]?d[c][i-1]:best+s[i];
		}
	}
	best=s[n]-s[n-1];
	for(i=n-1;i>=c;i--)
	{
		sol=sol>d[k][i]+best?sol:d[k][i]+best;
		best=best>s[n]-s[i-1]?best:s[n]-s[i-1];
	}
	printf("%d\n",sol);	
}