#include <bits/stdc++.h>
using namespace std;
int n, m, dp[30100][210][3][2], num[30100], sum[30100], s[2][30100][2],
    ans = 0x80808080, ass[30100][2];
int main() {
  scanf("%d%d", &n, &m), memset(dp, 0x80, sizeof(dp));
  for (int i = 1; i <= n; i++) scanf("%d", &num[i]);
  for (int i = 1; i <= n; i++)
    dp[i][1][0][0] = max(dp[i - 1][1][0][0], 0) - num[i],
    dp[i][1][1][1] = max(dp[i - 1][1][1][1], 0) + num[i];
  for (int i = 1; i <= n; i++)
    dp[i][1][2][0] = max(dp[i - 1][1][2][0], dp[i][1][0][0]),
    dp[i][1][2][1] = max(dp[i - 1][1][2][1], dp[i][1][1][1]);
  for (int i = 1; i <= n; i++)
    for (int j = 2; j < m; j++) {
      dp[i][j][0][0] = max({dp[i - 1][j][0][0], dp[i - 1][j - 1][1][1],
                            dp[i - 1][j - 1][2][1]}) -
                       2 * num[i];
      dp[i][j][1][1] = max({dp[i - 1][j][1][1], dp[i - 1][j - 1][0][0],
                            dp[i - 1][j - 1][2][0]}) +
                       2 * num[i];
      dp[i][j][2][0] = max({dp[i - 1][j][2][0], dp[i - 1][j - 1][2][0],
                            dp[i - 1][j - 1][0][0], dp[i - 1][j][0][0]});
      dp[i][j][2][1] = max({dp[i - 1][j][2][1], dp[i - 1][j - 1][2][1],
                            dp[i - 1][j - 1][1][1], dp[i - 1][j][1][1]});
    }
  for (int i = n; i >= 1; i--)
    ass[i][0] = max(ass[i + 1][0], 0) - num[i],
    ass[i][1] = max(ass[i + 1][1], 0) + num[i];
  for (int i = m - 1; i < n; i++) {
    ans = max(ans, max(dp[i][m - 1][0][0], dp[i][m - 1][2][0]) + ass[i + 1][1]);
    ans = max(ans, max(dp[i][m - 1][1][1], dp[i][m - 1][2][1]) + ass[i + 1][0]);
  }
  printf("%d\n", ans);
  return 0;
}
