#include <bits/stdc++.h>
using namespace std;
int const MAXN = 815;
int const MAX_Q = 100100;
int const MAX_CH = 100100;
long long const LL_INF = 1000000000000000009LL;
int const INT_INF = 1000000000;
int const MAX_TREE = 4194304;
int s[MAXN], p_sum[MAXN];
int dp_1[MAXN][MAXN], dp_2[MAXN][MAXN];
int tree_more[4 * MAX_TREE], tree_less[4 * MAX_TREE];
int vl_list[MAXN * MAXN];
inline int my_abs(int x) {
  if (x < 0) return -x;
  return x;
}
void update_MORE(int v, int new_val) {
  v += MAX_TREE * 3;
  tree_more[v] = new_val;
  while (v > 1) {
    tree_more[v >> 1] = max(tree_more[v], tree_more[v ^ 1]);
    v >>= 1;
  }
}
void update_LESS(int v, int new_val) {
  v += MAX_TREE * 3;
  tree_less[v] = new_val;
  while (v > 1) {
    tree_less[v >> 1] = max(tree_less[v], tree_less[v ^ 1]);
    v >>= 1;
  }
}
int find_max_MORE(int l, int r) {
  l += MAX_TREE * 3;
  r += MAX_TREE * 3;
  int ans = -INT_INF;
  while (l <= r) {
    if (l & 1) ans = max(ans, tree_more[l]);
    if (!(r & 1)) ans = max(ans, tree_more[r]);
    l = (l + 1) / 2;
    r = (r - 1) / 2;
  }
  return ans;
}
int find_max_LESS(int l, int r) {
  l += MAX_TREE * 3;
  r += MAX_TREE * 3;
  int ans = -INT_INF;
  while (l <= r) {
    if (l & 1) ans = max(ans, tree_less[l]);
    if (!(r & 1)) ans = max(ans, tree_less[r]);
    l = (l + 1) / 2;
    r = (r - 1) / 2;
  }
  return ans;
}
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> s[i];
  p_sum[0] = 0;
  for (int i = 1; i <= n; i++) p_sum[i] = p_sum[i - 1] + s[i];
  for (int i = 0; i <= n; i++)
    for (int len = 0; len <= n; len++) dp_1[i][len] = -INT_INF;
  for (int i = 1; i <= n; i++)
    for (int len = 1; len <= i; len++)
      if (1 + (n - i) >= k) dp_1[i][len] = 0;
  for (int i = 0; i < 4 * MAX_TREE; i++) tree_more[i] = tree_less[i] = -INT_INF;
  for (int q = 2; q <= k; q++) {
    for (int i = 0; i <= n; i++)
      for (int len = 0; len <= n; len++) dp_2[i][len] = -INT_INF;
    int vl_list_len = 0;
    for (int last_p = 1; last_p <= n; last_p++) {
      for (int i = last_p; i <= n; i++) {
        int val = p_sum[i] - p_sum[last_p - 1];
        int len = i - last_p + 1;
        int &t = dp_2[i][len];
        t = max(t, find_max_MORE(val, MAX_TREE - 1) - val);
        t = max(t, find_max_LESS(-MAX_TREE, val) + val);
      }
      int b = last_p;
      for (int a = b; a >= 1; a--)
        if (dp_1[b][b - a + 1] != -INT_INF) {
          int VL = p_sum[b] - p_sum[a - 1];
          update_MORE(VL, dp_1[b][b - a + 1] + VL);
          update_LESS(VL, dp_1[b][b - a + 1] - VL);
          vl_list[vl_list_len++] = VL;
        }
    }
    for (int j = 0; j < vl_list_len; j++) {
      update_MORE(vl_list[j], -INT_INF);
      update_LESS(vl_list[j], -INT_INF);
    }
    for (int i = 0; i <= n; i++)
      for (int len = 0; len <= n; len++) dp_1[i][len] = dp_2[i][len];
  }
  int mx = 0;
  for (int i = 1; i <= n; i++)
    for (int len = 1; len <= n; len++) mx = max(mx, dp_1[i][len]);
  cout << mx;
  return 0;
}
