#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <random>
#include <string>
#include <fstream>
#include <limits.h>
using namespace std;
typedef long long ll;
std::random_device rd;
std::mt19937 gen(23432);

ll bruteforce_on_subset(deque<ll> v)
{
	if (v.size() == 1)
	{
		return v[0];
	}
	ll x_first = v.front();
	ll x_last = v.back();
	v.pop_front();
	v.pop_back();
	v.push_back(x_last - x_first);
	ll res = bruteforce_on_subset(v);
	v.pop_back();
	v.push_front(x_first - x_last);
	res = max(res,bruteforce_on_subset(v));
	v.push_front(x_first);
	v.push_back(x_last);
	return res;
}

ll bruteforce(const vector<ll>& v, int pos, int k, deque<ll>& current_set)
{
	if (pos == v.size())
	{
		if (current_set.size() == k)
			return bruteforce_on_subset(current_set);
		return 0;
	}
	ll sol = bruteforce(v, pos + 1, k, current_set);
	current_set.push_back(v[pos]);
	sol = max(sol,bruteforce(v, pos + 1, k, current_set));
	current_set.pop_back();
	return sol;
}

ll solve_given_subset(const vector<ll>& v)
{
	if (v.size() == 1)
		return v[0];
	
	vector<ll> prefix_sums(v.size());
	vector<ll> suffix_sums(v.size());
	prefix_sums[0] = v[0];
	int n = v.size();
	for (int i = 1; i < n; i++)
		prefix_sums[i] = prefix_sums[i - 1] + v[i];
	
	suffix_sums[n - 1] = v[n - 1];
	for (int i = n-2; i >= 0; i--)
		suffix_sums[i] = suffix_sums[i + 1] + v[i];
	
	ll max_val = LLONG_MIN;
	for (int i = 0; i < n-1; i++)
	{
		ll sol1 = abs(prefix_sums[i] - suffix_sums[i+1]);
		max_val = max(max_val, sol1);
	}
	return max_val;
}

void print_dp_matrix(const vector<vector<vector<ll>>>& v)
{
	for (int t = 0; t < 2; t++)
	{
		for (int i = 0; i < v.size(); i++)
		{
			for (int j = 0; j < v[0].size(); j++)
			{
				cout << v[i][j][t] << " ";
			}
			cout << "\n";
		}
		cout << "\n";
	}
}

ll solve_dp(const vector<ll>& v, int k)
{
	int n = v.size();
	vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(k+1, vector<ll>(2, INT_MIN)));
	dp[0][0][0] = 0;
	for (int pos = 1; pos <= n; pos++)
	{
		dp[pos][0][0] = 0;
		dp[pos][0][1] = INT_MIN;
		for (int taken = 1; taken <= min(pos,k); taken++)
		{
			dp[pos][taken][0] = max(dp[pos - 1][taken][0], dp[pos - 1][taken - 1][0] + v[pos-1]);
			if (pos == 1)
				dp[pos][taken][1] = INT_MIN;
			else
				dp[pos][taken][1] = max(dp[pos - 1][taken][1], max(dp[pos - 1][taken - 1][1] - v[pos - 1], dp[pos - 1][taken - 1][0] - v[pos - 1]));
		}

		print_dp_matrix(dp);
	}
	ll res = LLONG_MIN;
	for (int i = 0; i <= n; i++)
	{
		if (dp[i][k][1] != INT_MIN)
		{
			res = max(res, abs(dp[i][k][1]));
		}
	}
	return res;
}

ll solve(vector<ll> v, int k)
{
	ll sol1 = solve_dp(v, k);
	/*for (int i = 0; i < v.size(); i++)
		v[i] = -v[i];
	ll sol2 = solve_dp(v, k);*/
	return sol1;
}

vector<ll> rand_vec(int n)
{
	vector<ll> v(n);

	std::uniform_int_distribution<> dist(-100, 100);
	for (int i = 0; i < n; i++)
	{
		v[i] = dist(gen);
	}
	return v;
}

void test()
{
	uniform_int_distribution<> n_dist(2, 3);

	for (int t = 1; t < 100; t++)
	{
		ofstream outfile(to_string(t) + ".in");
		int n = n_dist(gen);
		uniform_int_distribution<> k_dist(2, n);
		int k = k_dist(gen);
		auto v = rand_vec(n);
		/*outfile << n << " " << k << "\n";
		for (ll i: v)
		{
			outfile << i << " ";
		}
		outfile << "\n";*/

		deque<ll> current_set;
		ll sol1 = bruteforce(v,0,k,current_set);
		deque<ll> d(v.begin(), v.end());
		ll sol2 = solve(v, k);
		if (sol1 != sol2)
		{
			solve(v, k);
			current_set.clear();
			bruteforce(v, 0, k, current_set);
			cout << sol1 << " " << sol2 << "\n";
			for (ll i: v)
				cout << i << " ";
			
			cout << "wa\n";
		}
		else
		{
			cout << "ok\n";
		}
	}
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	//test();
	int n, k; cin >> n >> k;
	vector<ll> v(n);
	for (int i = 0; i < n; i++)
		cin >> v[i];
	if (n <= 10)
	{
		deque<ll> current_set;
		cout << bruteforce(v, 0, k, current_set) << "\n";
	}
	else if (n == k)
	{
		cout << solve_given_subset(v) << "\n";
	}
	else
	{
		cout << solve_dp(v, k);
	}

	return 0;
}