#include <bits/stdc++.h>
using namespace std;
int dp[30006][205][4];
int a[30006];
int n, k;
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= k; j++)
      for (int t = 0; t < 4; t++) dp[i][j][t] = -1e9 - 1e7;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= k; j++) {
      int mul = 2 - (j == 1 || j == k);
      dp[i][j][0] =
          max(dp[i - 1][j][0], max(dp[i - 1][j - 1][1], dp[i - 1][j - 1][3])) +
          a[i] * mul;
      if (j == 1) dp[i][j][0] = max(dp[i][j][0], a[i] * mul);
      dp[i][j][1] =
          max(dp[i - 1][j][1], max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][2])) -
          a[i] * mul;
      if (j == 1) dp[i][j][1] = max(dp[i][j][1], -a[i] * mul);
      dp[i][j][2] =
          max(dp[i - 1][j][2], max(dp[i - 1][j - 1][2], dp[i - 1][j - 1][0]));
      dp[i][j][3] =
          max(dp[i - 1][j][3], max(dp[i - 1][j - 1][3], dp[i - 1][j - 1][1]));
    }
  int res = -1e9 - 1e7;
  for (int i = k; i <= n; i++) res = max(res, max(dp[i][k][0], dp[i][k][1]));
  cout << res;
  return 0;
}
