#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void mx(T& x, const T& y) {
  if (x < y) x = y;
}
const int MAX_A = 4000000;
const int N = 400;
const int K = 50;
const int INF = 1000000000;
int dp[K + 1][N][N + 1];
int treePlus[1 << 18];
int treeMinus[1 << 18];
vector<int> sums;
inline void treeSet(int dest, int val, int l, int r, int x) {
  mx(treePlus[x], val + sums[dest]);
  mx(treeMinus[x], val - sums[dest]);
  if (r - l != 1) {
    int m = (l + r) >> 1;
    if (dest < m) {
      treeSet(dest, val, l, m, 2 * x + 1);
    } else {
      treeSet(dest, val, m, r, 2 * x + 2);
    }
  }
}
inline int treeMax(int* tree, int ql, int qr, int l, int r, int x) {
  if (ql <= l && r <= qr) {
    return tree[x];
  }
  if (r <= ql || qr <= l || tree[x] == -INF) {
    return -INF;
  }
  int m = (l + r) >> 1;
  return max(treeMax(tree, ql, qr, l, m, 2 * x + 1),
             treeMax(tree, ql, qr, m, r, 2 * x + 2));
}
int main() {
  ios_base::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < (n); ++i) {
    cin >> a[i];
  }
  vector<int> p(n + 1);
  p[0] = 0;
  for (int i = 0; i < (n); ++i) {
    p[i + 1] = p[i] + a[i];
  }
  for (int l = 0; l < n; ++l) {
    for (int r = l + 1; r <= n; ++r) {
      sums.push_back(p[r] - p[l]);
    }
  }
  sort(sums.begin(), sums.end());
  sums.erase(unique(sums.begin(), sums.end()), sums.end());
  for (int kk = 2; kk <= k; ++kk) {
    for (int i = 0; i < (1 << 18); ++i) {
      treePlus[i] = -INF;
      treeMinus[i] = -INF;
    }
    for (int l = 0; l < n; ++l) {
      for (int prevL = 0; prevL < l; ++prevL) {
        int score = dp[kk - 1][prevL][l];
        if (score != -INF) {
          int sum = p[l] - p[prevL];
          int index = lower_bound(sums.begin(), sums.end(), sum) - sums.begin();
          treeSet(index, score, 0, sums.size(), 0);
        }
      }
      for (int r = l + 1; r <= n; ++r) {
        int sum = p[r] - p[l];
        int index = lower_bound(sums.begin(), sums.end(), sum) - sums.begin();
        int s1 = treeMax(treePlus, index, sums.size(), 0, sums.size(), 0);
        int s2 = treeMax(treeMinus, 0, index + 1, 0, sums.size(), 0);
        if (s1 != -INF) {
          s1 = s1 - sum;
        }
        if (s2 != -INF) {
          s2 = s2 + sum;
        }
        dp[kk][l][r] = max(s1, s2);
      }
    }
  }
  int ans = 0;
  for (int l = 0; l < n; ++l) {
    for (int r = l + 1; r <= n; ++r) {
      mx(ans, dp[k][l][r]);
    }
  }
  cout << ans << endl;
  return 0;
}
