#include <fstream>

using namespace std;
ifstream fin("ferma.in");
ofstream fout("ferma.out");
int a[5][10005];
int n,k;
int s[10005];



int main()
{  int i,j,maxi=0,nr,sol;
   fin>>n>>k;
   for(i=1;i<=n;++i)
   { fin>>s[i];
    s[i]+=s[i-1];
   }
  nr=0;
   for(i=1;i<=n;++i)
   { nr+=s[i]-s[i-1];
       if(nr>maxi) maxi=nr;
       if(nr<0) nr=0;
       a[1][i]=maxi;
   }


   for(i=2;i<=k;++i)
   {
   maxi=0;
       for(j=1;j<=n;++j)
       {
        a[2][j]=max(a[2][j-1],a[1][maxi]+s[j]-s[maxi]);
        if(a[1][maxi]-s[maxi] <= a[1][j]-s[j])
               maxi=j;
       }

       for(j=1;j<=n;++j)
        a[1][j]=a[2][j];
   }
   sol=a[1][n];

  a[1][1]=s[1];
   for(i=2;i<=n;++i)
    a[1][i]=max(a[1][i-1],s[i]);

    for(i=2;i<=k;++i)
   {
   maxi=1;
       for(j=1;j<=n;++j)
       {
        a[2][j]=max(a[2][j-1],a[1][maxi]+s[j]-s[maxi]);
        if(a[1][maxi]-s[maxi] <= a[1][j]-s[j])
               maxi=j;
     if(i==k)
         sol=max(sol, a[2][j]  +s[n]-s[j] );
       }

       for(j=1;j<=n;++j)
        a[1][j]=a[2][j];
   }
   fout<<sol;

    return 0;
}