#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
#define int long long
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
/*
大概有个 dp i 0/1/2

表示我这次选完了/选了 -/选了 +

转移是 
dp i 0->dp i 1-a[i] 
dp i 0->dp i 2+a[i] 
...

这三个都是图的吗？

可以先去观察 a，这里已经有 70 分了。

可以进行一个分治？

(i,si,0/1/2,0/1/2) 表示区间的左边和右边的段选择的 +/-/没有 

然后可以做闵可夫斯基和，对吗？

(0,1) (1,5) (2,6)

(0,5) (1,5) (2,4)


*/
const int mxn=4e5+5;
int n,m,op;
int a[mxn];
#define ls w<<1
#define rs ls|1
vector<int> res[mxn][3][3];//+/-/没有，第一维是选完了几个吧？ 
/*
res[ls][x][0]和res[rs][1][y]合并

res[ls][x][1]和res[rs][0][y]合并
*/
vector<int> merge(vector<int> x,vector<int> y)
{
//	assert(x.size()&&y.size());
	if(x.empty()||y.empty()) return {};
	vector<int> res{x[0]+y[0]};
	int i=1,j=1,k;
	while(i<x.size()&&j<y.size())
		if(x[i]-x[i-1]>y[j]-y[j-1])
			res.push_back(res.back()+x[i]-x[i-1]),i++;
		else
			res.push_back(res.back()+y[j]-y[j-1]),j++;
	while(i<x.size())
		res.push_back(res.back()+x[i]-x[i-1]),i++;
	while(j<y.size())
		res.push_back(res.back()+y[j]-y[j-1]),j++;
//	vector<int> res(x.size()+y.size()-1);
//	int i,j;
//	for(i=0;i<res.size();i++) res[i]=-1e18;
//	for(i=0;i<x.size();i++)
//		for(j=0;j<y.size();j++)
//			res[i+j]=max(res[i+j],x[i]+y[j]);
	return res;
}
vector<int> getmax(vector<int> x,vector<int> y)
{
	if(x.size()<y.size()) swap(x,y);
//	assert(x.size()==y.size());
	for(int i=0;i<y.size();i++)
		x[i]=max(x[i],y[i]);
	return x;
}
//void checktu(vector<int> a)
//{
//	int pre=5e18,i;
//	for(i=1;i<a.size();i++)
//	{
//		int tp=a[i]-a[i-1];
//		assert(tp<=pre);
//		pre=tp;
//	}
//}
void solve(int w,int l,int r)
{
	if(l==r)
	{
		res[w][0][2]=res[w][2][0]={a[l]};
		res[w][1][2]=res[w][2][1]={-a[l]};
		res[w][2][2]={0,0};
		return;
	}
	int mid=l+r>>1;
	solve(ls,l,mid),solve(rs,mid+1,r);
	int x,y;
	for(x=0;x<3;x++)
		for(y=0;y<3;y++)
		{
//			cout<<"qwq "<<x<<' '<<y<<endl;
			res[w][x][y]=getmax(merge(res[ls][x][0],res[rs][1][y]),merge(res[ls][x][1],res[rs][0][y]));
			if(res[w][x][y].size()) res[w][x][y].insert(res[w][x][y].begin(),-1e18);
//			if(x==2&&y==2&&res[w][x][y].size()>1) cout<<l<<' '<<r<<':'<<res[w][x][y][1]<<endl;
			res[w][x][y]=getmax(res[w][x][y],res[ls][x][y]);
			res[w][x][y]=getmax(res[w][x][y],res[rs][x][y]);
//			{
//				
//				for(auto p:res[w][x][y])
//					cout<<p<<',';
//				puts("");
//			}
//			cout<<"qwq "<<x<<' '<<y<<' '<<res[w][x][y].size()<<endl;
			res[w][x][y]=getmax(res[w][x][y],merge(res[ls][x][2],res[rs][2][y]));
//			if(x==2&&y==2&&res[w][x][y].size()>1) cout<<l<<' '<<r<<':'<<res[w][x][y][1]<<endl;
//			{
//				cout<<l<<' '<<r<<'#'<<x<<' '<<y<<':';
//				for(auto p:res[w][x][y])
//					cout<<p<<',';
//				puts("");
//			}
		}
//	for(x=0;x<3;x++)
//		for(y=0;y<3;y++)
//			checktu(res[w][x][y]);
//	cout<<l<<' '<<r<<':'<<res[w][2][2][1]<<endl;		
}
signed main()
{
//	system("fc out tower3.ans");
	n=read(),m=read(),op=2;
	for(int i=1;i<=n;i++)
		a[i]=read();
	solve(1,1,n);
	if(op==1) cout<<res[1][2][2][m];
	else
	{
		for(int i=1;i<=m;i++)
			printf("%lld\n",res[1][2][2][i]);
	}
}
/*
7 1 1
42 68 35 1 70 25 79 

2 2 2
5 10

3 3 2
1 2 3


5 5 2
1 2 3 4 5

5 5 2
1 7 5 8 10

5 5 2
1 2 1 2 1

*/