#include <bits/stdc++.h>
using namespace std;
const int N = 30005;
int dp1[2][N], dp2[2][N], dp[2][N];
int a[N], sum[N];
int main() {
  int n, K;
  scanf("%d%d", &n, &K);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i];
  int pre = 0;
  for (int i = 1; i <= n; ++i) {
    dp1[1][i] = max(a[i], a[i] + pre);
    pre = dp1[1][i];
  }
  pre = 0;
  for (int i = 1; i <= n; ++i) {
    dp2[1][i] = max(-a[i], pre - a[i]);
    pre = dp2[1][i];
  }
  for (int i = 2; i <= n; ++i) {
    dp1[1][i] = max(dp1[1][i], dp1[1][i - 1]);
    dp2[1][i] = max(dp2[1][i], dp2[1][i - 1]);
  }
  for (int k = 2; k <= K; ++k) {
    int cur = k & 1, pre = cur ^ 1;
    memset(dp1[cur], -0x3f, sizeof(dp1[cur]));
    memset(dp2[cur], -0x3f, sizeof(dp2[cur]));
    int val1 = -0x3f3f3f3f, val2 = -0x3f3f3f3f;
    for (int i = 1; i <= n; ++i) {
      dp[cur][i] = max(val1 - sum[i], val2 + sum[i]);
      val1 = max(val1, dp1[pre][i] + sum[i]);
      val2 = max(val2, dp2[pre][i] - sum[i]);
    }
    val1 = val2 = -0x3f3f3f3f;
    for (int i = 1; i <= n; ++i) {
      dp1[cur][i] = max(val1, val2 + 2 * sum[i]);
      val1 = max(val1, dp1[pre][i]);
      val2 = max(val2, dp2[pre][i] - 2 * sum[i]);
    }
    val1 = val2 = -0x3f3f3f3f;
    for (int i = 1; i <= n; ++i) {
      dp2[cur][i] = max(val1 - 2 * sum[i], val2);
      val1 = max(val1, dp1[pre][i] + 2 * sum[i]);
      val2 = max(val2, dp2[pre][i]);
    }
    for (int i = 2; i <= n; ++i) {
      dp1[cur][i] = max(dp1[cur][i], dp1[cur][i - 1]);
      dp2[cur][i] = max(dp2[cur][i], dp2[cur][i - 1]);
    }
  }
  int ans = -0x3f3f3f3f;
  for (int i = 1; i <= n; ++i) ans = max(ans, dp[K & 1][i]);
  printf("%d\n", ans);
  return 0;
}
