#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cassert>

using namespace std;

const int MaxN = 10005;
const int MaxK = 1005;

int N, K, Sum[MaxN];
int DP[MaxK][MaxN], Solution;

void SolveDP() {
    for (int i = 1; i <= K; ++i) {
        for (int j = 1, MaxDP = 0; j <= N; ++j) {
            DP[i][j] = max(DP[i][j], DP[i][j - 1]);
            DP[i][j] = max(DP[i][j], Sum[j] + MaxDP);
            MaxDP = max(MaxDP, DP[i - 1][j] - Sum[j]);
        }
    }
}

void Solve() {
    SolveDP();
    Solution = DP[K][N];
    memset(DP, 0, sizeof(DP));
    for (int i = 1; i <= N; ++i)
        DP[1][i] = Sum[i];
    SolveDP();
    for (int i = 1; i <= N; ++i)
        Solution = max(Solution, DP[K][i] + Sum[N] - Sum[i]);
}

void Read() {
    assert(freopen("ferma.in", "r", stdin));
    assert(scanf("%d %d", &N, &K) == 2);
    for (int i = 1; i <= N; ++i) {
        int Value; assert(scanf("%d", &Value) == 1);
        Sum[i] = Sum[i - 1] + Value;
    }
}

void Print() {
    assert(freopen("ferma.out", "w", stdout));
    printf("%d\n", Solution);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}