#include <bits/stdc++.h>
using namespace std;
int a[410], s[410], dp[60][410][2];
void su(int &a, int b) {
  if (b > a) a = b;
}
void lemon() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (n); i++) scanf("%d", &a[i]);
  for (int i = (1); i <= (n); i++) s[i] = s[i - 1] + a[i];
  for (int k = (1); k <= (m); k++)
    for (int i = (1); i <= (n); i++)
      for (int flag = (0); flag <= (1); flag++) dp[k][i][flag] = -1000000000;
  for (int i = (1); i <= (n); i++)
    for (int j = (i); j <= (n); j++) {
      su(dp[1][j][0], -(s[j] - s[i - 1]));
      su(dp[1][j][1], s[j] - s[i - 1]);
    }
  for (int k = (1); k <= (m - 1); k++)
    for (int i = (1); i <= (n); i++)
      for (int flag = (0); flag <= (1); flag++)
        if (dp[k][i][flag] != -1000000000) {
          for (int j = (i + 1); j <= (n); j++) {
            if (k != m - 1) su(dp[k + 1][j][flag], dp[k][i][flag]);
            if (flag == 0) {
              if (k == m - 1)
                su(dp[k + 1][j][1 - flag], dp[k][i][flag] + (s[j] - s[i]));
              else
                su(dp[k + 1][j][1 - flag], dp[k][i][flag] + (s[j] - s[i]) * 2);
            } else {
              if (k == m - 1)
                su(dp[k + 1][j][1 - flag], dp[k][i][flag] - (s[j] - s[i]));
              else
                su(dp[k + 1][j][1 - flag], dp[k][i][flag] - (s[j] - s[i]) * 2);
            }
          }
        }
  int ans = -1000000000;
  for (int i = (1); i <= (n); i++)
    for (int flag = (0); flag <= (1); flag++) su(ans, dp[m][i][flag]);
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(true);
  lemon();
  return 0;
}
