#include <bits/stdc++.h>
const int MAX_N = (int)1e5 + 123;
const double eps = 1e-6;
const int inf = (int)1e9 + 123;
using namespace std;
int n, k;
int a[405];
int dp[2][405][405];
int sum[405];
int neg[405], pos[405];
void clear(bool tp) {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) dp[tp][i][j] = -inf;
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
  clear(0);
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) dp[0][i][j] = 0;
  for (int counter = 2, now; counter <= k; counter++) {
    now = counter % 2;
    clear(now);
    neg[0] = pos[0] = -inf;
    for (int j = 1; j <= n; j++) {
      neg[j] = neg[j - 1], pos[j] = pos[j - 1];
      for (int i = 1; i <= j; i++) {
        neg[j] = max(neg[j], dp[(now ^ 1)][i][j] - (sum[j] - sum[i - 1]));
        pos[j] = max(pos[j], dp[(now ^ 1)][i][j] + (sum[j] - sum[i - 1]));
      }
    }
    for (int i = 1; i <= n; i++)
      for (int j = i; j <= n; j++) {
        dp[now][i][j] = max(dp[now][i][j], neg[i - 1] + (sum[j] - sum[i - 1]));
        dp[now][i][j] = max(dp[now][i][j], pos[i - 1] - (sum[j] - sum[i - 1]));
      }
  }
  int ans = -inf;
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) ans = max(ans, dp[k % 2][i][j]);
  cout << ans;
  return 0;
}
