#include<stdio.h>
#include<string.h>

#define maxim(a,b) (a>b ? a : b)

int n,k,p[10005];
int d[2][10005];
int v[10005],s[10005];

void calc(int tip)
{
    int i,j;
    
    for(i=1+tip;i<=k;i++)
    {
        for(j=1;j<=n;j++)
            p[j]=maxim(p[j-1],d[(i-1)&1][j]-s[j]);
        for(j=i;j<=n;j++)
            d[i&1][j]=maxim(d[i&1][j-1],p[j-1]+s[j]);
    }
}

int main ()
{
    int i,sol1,sol2;
    freopen("ferma.in","r",stdin);
    freopen("ferma.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
        s[i]=s[i-1]+v[i];
    }
    
    calc(0);
    sol1=d[k&1][n];

    memset(d,0,sizeof(d));

    d[1][1]=s[1];
    for(i=2;i<=n;i++)
        d[1][i]=maxim(d[1][i-1],s[i]);
    calc(1);
    sol2=d[k&1][n];
    for(i=n-1;i>=1;i--)
        sol2=maxim(sol2,d[k&1][i]+s[n]-s[i]);
    
    printf("%d\n", maxim(0,maxim(sol1,sol2)));
    
    return 0;
}