#include<bits/stdc++.h>
//#define endl '\n'
using namespace std;
typedef long long ll;
ll i,j,p,q,n,m,k,t,a[30006],s[30006];
ll dp[30006][206];
void read()
{
	freopen("monkeys.in","r",stdin);
    freopen("monkeys.out","w",stdout);
}
void solve()
{
    cin>>n>>k;
    s[0]=0;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        //cout<<a[i]<<endl;
        s[i]=s[i-1]+a[i];
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=k;j++)
        {
            dp[i][j]=0;
        }
    }
    for(j=1;j<=k;j+=2)
    {
        //cout<<j<<" jjjj "<<endl;
        for(i=j;i<=n;i++)
        {
            if(j==1 && i>1)break;
            for(p=i+1;p<=n-(k-j-1);p++)
            {
                if(j==k-1 && p!=n)continue;
                //cout<<i<<" "<<p<<" : "<<endl;
                //cout<<a[i]<<" "<<s[p]-s[i]<<endl;
                //cout<<a[p]<<" "<<s[p-1]-s[i-1]<<endl;
                //if(j-2>=0)cout<<dp[i-1][j-2]<<endl;
                if(j-2>=0)
                    q=dp[i-1][j-2];
                else q=0;
                ll val = q+max(abs(a[i]-(s[p]-s[i])),abs(a[p]-(s[p-1]-s[i-1])));
                if(val<dp[p][j])break;
                dp[p][j]=max(dp[p][j],val);
            }
        }
    }
    cout<<dp[n][k-1]<<endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	solve();
	return 0;
}