#include <stdio.h>

#define maxn 10010
#define maxk 1001


long n, i, j, k, v[maxn], s[maxn], m, sol;
long d[maxk][maxn];

long max(long a, long b)
{
    if(a<b) return b;
    return a;
}

void dinamica(long tip)
{
    for(i=1; i<=k; i++)
    {
        for(j=0; j<=n; j++)
        {
            d[i][j]=-1100000000;
        }
    }
    if(tip==2) 
    {
        for(i=1; i<=n; i++)
        {
            d[1][i]=max(d[1][i-1], s[i]);
          //  printf("%d ", d[1][i]);
        }
    //    printf("\n");
    }
    for(i=tip; i<=k; i++)
    {
        m=-1100000000;
        for(j=i; j<=n; j++)
        {
            if(d[i-1][j-1]-s[j-1]>m)
            {
                m=d[i-1][j-1]-s[j-1];
          //      printf("*");
            }
            d[i][j]=max(s[j]+m, d[i][j-1]);
     //       printf("%d ", d[i][j]);
        }
   //     printf("\n");
    }
}
    

int main()
{
    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];
    }
    dinamica(1);
    sol=d[k][n];
  //  printf("\n");
    dinamica(2);
    for(i=1; i<=n; i++)
    {
    //    printf("%d ", d[k][i]);
        if(d[k][i]+s[n]-s[i]>sol) sol=d[k][i]+s[n]-s[i];
    }
    printf("%d\n", sol);
    return 0;
}