#include <bits/stdc++.h>
using namespace std;
int c[30005], n, dp[205][30005][3], b[5][3];
int &dpc(int i, int k, int t) { return dp[k][i][t + 1]; }
int &bc(int i, int j) { return b[i + 2][j + 1]; }
int main() {
  int K;
  scanf("%d %d", &n, &K);
  for (int i = (1); i < (n + 1); i++) {
    scanf("%d", c + i);
    c[i] += c[i - 1];
  }
  for (int k = (1); k < (K + 1); k++) {
    for (int t = (-1); t < (2); t++) {
      dpc(n, k, t) = -1e9;
      for (int i = (-2); i < (3); i++)
        for (int j = (-1); j < (2); j++)
          bc(i, j) = i * c[n] + dpc(n, k - 1, -j);
      for (int i = n; i >= 0; i--) {
        if (i != n) {
          dpc(i, k, t) = dpc(i + 1, k, t);
          for (int nek = (-1); nek < (2); nek++)
            if ((k == 1) == (nek == 0))
              dpc(i, k, t) =
                  max(dpc(i, k, t), bc(t + nek, nek) - (t + nek) * c[i]);
        }
        for (int I = (-2); I < (3); I++)
          for (int j = (-1); j < (2); j++)
            bc(I, j) = max(bc(I, j), I * c[i] + dpc(i, k - 1, -j));
      }
    }
  }
  printf("%d\n", dpc(0, K, 0));
}
