#include<bits/stdc++.h>
using namespace std;

const int nmax=3e4+42,kmax=202;
const long long INF=1e18;

int n,k,inp[nmax];

long long pref[nmax];

long long dp[nmax][kmax];

long long solve()
{
    scanf("%i%i",&n,&k);
    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    for(int i=1;i<=n;i++)pref[i]=pref[i-1]+inp[i];

    bool odd=k%2;
    k=k/2;

    for(int i=0;i<=n;i++)
        for(int j=0;j<=k;j++)
            dp[i][j]=-INF;

    dp[0][0]=0;

    for(int k_now=1;k_now<=k;k_now++)
    {
        long long MX_case_1=-INF,MX_case_2=-INF;

        for(int i=1;i<=n;i++)
        {
            //cout<<"i= "<<i<<" k_now= "<<k_now<<endl;

            if(i<2*k_now)continue;

            int j=i-2;

            MX_case_1=max(MX_case_1,dp[j][k_now-1]-pref[j]);
            dp[i][k_now]=max(dp[i][k_now],MX_case_1+pref[i]-2*inp[i]);

            MX_case_2=max(MX_case_2,dp[j][k_now-1]-pref[j]-2*inp[j+1]);
            dp[i][k_now]=max(dp[i][k_now],MX_case_2+pref[i]);

            //cout<<i<<" "<<k_now<<" -> "<<dp[i][k_now]<<" "<<MX_case_1<<" "<<MX_case_2<<endl;
        }
    }

    long long outp=dp[n][k];

    if(odd)
    {
        for(int i=1;i<=n;i++)
            outp=max(outp,dp[i-1][k]+pref[n]-pref[i]);
    }

    return outp;
}

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

    int t=1;
    while(t)
    {
        t--;
        printf("%lld\n",solve());
    }

    return 0;
}
/*
6 4
2002 505 2013 1 4 5 	4520

7 2
10 24 11 2021 12 8 2022	4088

10 7
1 2 3 4 5 6 7 8 9 10	37
*/