#include <fstream>
#include <algorithm>

using namespace std;

int N, K;
int V[10002], S[10002];
int Smax[2][1002][10002];

int main()
{
    ifstream fin("ferma.in");
    ofstream fout("ferma.out");

    fin >> N >> K;
    for (int i = 1; i <= N; ++i)
    {
        fin >> V[i];
        S[i] = S[i - 1] + V[i];
    }

    int act = 0, old = 1;

    for (int i = 1; i <= K; ++i)
    {
        int maxnow = -S[1];
        for (int j = 2; j <= N; ++j)
        {
            Smax[0][i][j] = max(Smax[0][i][j - 1], maxnow + S[j]);
            maxnow = max(maxnow, Smax[0][i - 1][j] - S[j]);
        }
    }
    for (int i = 1; i <= K; ++i)
    {
        int maxnow = 0;
        for (int j = 1; j <= N; ++j)
        {
            Smax[1][i][j] = max(Smax[1][i][j - 1], maxnow + S[j]);
            maxnow = max(maxnow, Smax[1][i - 1][j] - S[j]);
        }
    }

    int maxnow = 0, result;
    for (int i = 1; i < N; ++i)
        maxnow = max(maxnow, Smax[1][K][i] - S[i]);
    result = maxnow + S[N];

    fout << max(result, max(Smax[0][K][N], Smax[1][K][N]));


    fin.close();
    fout.close();
}