#include <bits/stdc++.h>
using namespace std;
const int N = 405, K = 52, INF = 2e9;
int dp[K][2][N];
int a[N];
int sum[N];
inline int contr(int m, int k, int ps, int cs) {
  int con = 0;
  if (k > 1) {
    if (ps == 0)
      con++;
    else
      con--;
  }
  if (k < m) {
    if (cs == 0)
      con--;
    else
      con++;
  }
  return con;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    sum[i] = a[i] + sum[i - 1];
  }
  for (int k = 1; k <= m; k++) {
    dp[k][0][0] = dp[k][1][0] = -INF;
    for (int cs = 0; cs <= 1; cs++) {
      for (int i = 1; i <= n; i++) dp[k][cs][i] = dp[k][cs][i - 1];
      for (int ps = 0; ps <= 1; ps++) {
        for (int i = 1; i <= n; i++) {
          int con = contr(m, k, ps, cs);
          for (int j = 1; j <= i; j++) {
            dp[k][cs][i] =
                max(dp[k][cs][i],
                    dp[k - 1][ps][j - 1] - sum[j - 1] * con + sum[i] * con);
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    ans = max(ans, dp[m][0][i]);
    ans = max(ans, dp[m][1][i]);
  }
  cout << ans << endl;
}
