#include <cstdio>

const int Mn = 10010, Mk = 1005, INF = 1000000000;

int n, k, rez, s[Mn], d[Mk][Mn];

void read() {
    freopen("ferma.in", "r", stdin);
    freopen("ferma.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++ i) {
        scanf("%d", &s[i]);
        s[i] = s[i - 1] + s[i];
    }
}

inline int max(int x, int y) {
    return x < y ? y : x;
}

void init (int d[Mk][Mn], int val) {
    for (int i = 1; i < Mk; ++ i)
        for (int j = 0; j < Mn; ++ j)
            d[i][j] = val;
}

void din1() {
    int Mc;
    for (int i = 1; i <= k; ++ i) {
        Mc = - INF;
        for (int j = i; j <= n; ++ j) {
            if (d[i - 1][j - 1] - s[j - 1] > Mc)
                Mc = d[i - 1][j - 1] - s[j - 1];
            d[i][j] = max(s[j] + Mc, d[i][j - 1]);
        }
    }
}

void din2() {
    for (int  j = 1; j <= n; ++ j)
        d[1][j] = max(s[j], d[1][j - 1]);
    int Mc;
    for (int i = 2; i <= k; ++ i) {
        Mc = - INF;
        for (int j = i; j <= n; ++ j) {
            if (d[i - 1][j - 1] - s[j - 1] > Mc)
                Mc = d[i - 1][j - 1] - s[j - 1];
            d[i][j] = max(s[j] + Mc, d[i][j - 1]);
        }
    }
}

void solve() {
    init(d, - INF);
    din1();
    rez = d[n][k];
    init(d, - INF);
    din2();
}

void afis() {
    for (int j = 1; j <= n; ++ j)
        if (d[k][j] + s[n] - s[j] > rez)
            rez = d[k][j] + s[n] - s[j];
    printf("%d\n", rez);
}

int main() {
    read();
    solve();
    afis();
    return 0;
}