#include <bits/stdc++.h>
using namespace std;
using namespace std;
int ar[30005];
int dp1[30005][205][2], dp2[30005][205][2][5];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &ar[i]), ar[i] += ar[i - 1];
  fill(dp1[0][0], dp1[n][k] + 2, -1000000000);
  fill(dp2[0][0][0], dp2[n][k][1] + 5, -1000000000);
  dp1[0][0][0] = 0;
  dp1[0][0][1] = 0;
  for (int i = 0; i < 2; i++)
    for (int j = -2; j <= 2; j++) dp2[1][1][i][j + 2] = j * ar[1];
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= k; j++)
      for (int l = 0; l < 2; l++) {
        int &tmp = dp1[i][j][l];
        if (!j)
          tmp = 0;
        else {
          tmp = max(tmp, dp1[i - 1][j][l]);
          int l1 = (!l ? 0 : 2), l2 = l1 - 2;
          if (j == 1)
            l1--, l2++;
          else if (j == k)
            l1 = 1, l2 = -1;
          tmp = max(tmp, dp2[i][j][0][l1 + 2]);
          tmp = max(tmp, dp2[i][j][1][l2 + 2]);
        }
        for (int r = -1 - (l != 0); r <= 2 - (l != 0); r++)
          dp2[i + 1][j + 1][(l != 0)][r + 2] =
              max(dp2[i][j + 1][(l != 0)][r + 2], tmp) +
              r * (ar[i + 1] - ar[i]);
      }
  printf("%d\n", max(dp1[n][k][0], dp1[n][k][1]));
}
