#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1E9;
int N, K;
int a[405], sa[405];
int dp[55][405][2][2];
int main() {
  cin >> N >> K;
  for (int i = (1); i < (N + 1); i++) {
    scanf("%d", a + i);
    sa[i] = a[i] + sa[i - 1];
  }
  for (int k = (0); k < (K + 1); k++)
    for (int i = (0); i < (N + 1); i++)
      for (int t = (0); t < (2); t++)
        for (int e = (0); e < (2); e++) dp[k][i][t][e] = -INF;
  for (int i = (0); i < (N + 1); i++)
    for (int t = (0); t < (2); t++) dp[0][i][t][0] = 0;
  for (int k = (1); k < (K + 1); k++) {
    for (int i = (1); i < (N + 1); i++) {
      for (int j = (0); j < (i); j++) {
        int s = sa[i] - sa[j];
        for (int t = (0); t < (2); t++) {
          for (int e = (0); e < (2); e++) {
            if (dp[k - 1][j][t][e] == -INF) continue;
            if (k > 1) {
              dp[k][i][t][0] = max(dp[k][i][t][0], dp[k - 1][j][t][e]);
            }
            int nt = !t;
            int f = (k == 1 || k == K) ? 1 : 2;
            int ne = k == 1 ? 0 : 1;
            dp[k][i][nt][ne] = max(dp[k][i][nt][ne],
                                   dp[k - 1][j][t][e] + f * (nt == 0 ? s : -s));
          }
        }
      }
      for (int t = (0); t < (2); t++)
        for (int e = (0); e < (2); e++) {
          if (dp[k][i - 1][t][e] == -INF) continue;
          dp[k][i][t][e] = max(dp[k][i][t][e], dp[k][i - 1][t][e]);
        }
    }
  }
  int ans = max(dp[K][N][0][1], dp[K][N][1][1]);
  cout << ans << endl;
  return 0;
}
