#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int NMAX = 10010, KMAX = 1010;

int N, K, V[NMAX], Sum[NMAX], Best[KMAX][NMAX], Ans;

void BuildDp(int StartLine)
{
    for(int i = StartLine; i <= K; ++ i)
    {
        int CrtMax = Best[i - 1][i - 1] - Sum[i - 1];
        for(int j = i; j <= N; ++ j)
        {
            Best[i][j] = max(Best[i][j - 1], CrtMax + Sum[j]);
            CrtMax = max(CrtMax, Best[i - 1][j] - Sum[j]);
        }
    }
}

int main()
{
    freopen("ferma.in", "r", stdin);
    freopen("ferma.out", "w", stdout);

    scanf("%i %i", &N, &K);
    for(int i = 1; i <= N; ++ i)
    {
        scanf("%i", &V[i]);
        Sum[i] = Sum[i - 1] + V[i];
    }

    BuildDp(1); Ans = Best[K][N];
    Best[1][1] = Sum[1];
    for(int i = 2; i <= N; ++ i) Best[1][i] = max(Best[1][i - 1], Sum[i]);
    BuildDp(2);
    for(int i = 1; i <= N; ++ i)
        Ans = max(Ans, Best[K][i] + Sum[N] - Sum[i]);

    printf("%i\n", Ans);
}