#include <cstdio>
#include <fstream>

using namespace std;

#define FIN "ferma.in"
#define FOUT "ferma.out"
#define MAX_N 10005
#define MAX_K 1005

int L1[MAX_N];
int L2[MAX_N]; // liniile din dinmica

int D[MAX_N]; // deque
int A[MAX_N];
int S[MAX_N];

int N, K, i;
int BEST; //solutia
int li, lf; // indici deque

    inline int MAX (int a, int b) { if (a > b) return a; else return b; }

    void init ()
    {
         int i, Sc, M;
         
         for (i = 1; i <= N; ++i) S[i] = S[i - 1] + A[i];
         
         L1[1] = Sc = M = A[1];
         
         for (i = 2; i <= N; ++i)
         { 
             if (Sc < 0) Sc = A[i];
                else Sc += A[i];
             if (Sc > M) M = Sc;
             
             L1[i] = M;
         }
    }
    
    void DIN (int c)
    {
         D[++lf] = c;
         if (c > D[li]) D[lf = li] = c;
         while (D[lf] > D[lf - 1] && lf > li) D[lf - 1] = D[lf--];
    }

    void solve (void)
    {
         int i, j;
         
         init ();
         
       //  for (i = 1; i <= N; ++i)
       //    printf ("%d ", L1[i]);
         
         for (i = 2; i <= K; ++i)
         {
             memset (D, 0, sizeof (D));  li = 1; lf = 0;
             
             DIN (A[1]);
             for (j = 2; j <= N; ++j)
             {
                 L2[j] = MAX (L2[j - 1], D[li] + S[j]);
                 DIN(L1[j - 1] - S[j]);
             }
             
             memcpy (L1, L2, sizeof (L2));
         }
         
         BEST = L2[N];
         
         memset (L2, 0, sizeof (L2));
         memcpy (L1, S, sizeof (S));
         
         for (i = 2; i <= K; ++i)
         {
             memset (D, 0, sizeof (D));  li = 1; lf = 0;
             
             DIN (A[1]);
             for (j = 2; j <= N; ++j)
             {
                 L2[j] = MAX (L2[j - 1], D[li] + S[j]);
                 DIN(L1[j - 1] - S[j]);
             }
             
             memcpy (L1, L2, sizeof (L2));
         }
         
         for (i = 1; i <= N; ++i)
             BEST = MAX (BEST, L2[i] + S[N] - S[i]);
         
         printf ("%d\n", (int) (BEST));
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d",&N, &K);
        
        for (i = 1; i <= N; ++i) scanf ("%d", A + i);
        
        solve ();
        
        return 0;
    }