#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
const int SIZE = 30001;
int a[SIZE];
int sum[SIZE];
int dp[201][2][2];
int pre[2] = {-1, 1};
int pro[2] = {2, -2};
int nxt[2] = {-1, 1};
int back_mi[SIZE], back_ma[SIZE];
int main() {
  int N, K;
  scanf("%d%d", &N, &K);
  for (int i = 0; i < (N); ++i) scanf("%d", &(a[i + 1]));
  for (int i = (1); i < (N + 1); ++i) sum[i] = sum[i - 1] + a[i];
  back_mi[N] = back_ma[N] = sum[N];
  for (int i = N - 1; i >= 0; i--) {
    back_ma[i] = max(back_ma[i + 1], sum[i]);
    back_mi[i] = min(back_mi[i + 1], sum[i]);
  }
  for (int i = 0; i < (K); ++i)
    for (int j = 0; j < (2); ++j)
      for (int k = 0; k < (2); ++k) dp[i][j][k] = -INF;
  int an = 0;
  int mi = 0, ma = 0;
  for (int i = (1); i < (N); ++i) {
    for (int k1 = 0; k1 < (2); ++k1)
      for (int k2 = 0; k2 < (2); ++k2) {
        if (dp[K - 2][k1][k2] != -INF)
          an = max(an,
                   dp[K - 2][k1][k2] + sum[i] * (nxt[k1] + pro[k2]) +
                       max(back_ma[i + 1] * nxt[k2], back_mi[i + 1] * nxt[k2]));
      }
    for (int j = K - 2; j > 0; j--) {
      for (int k1 = 0; k1 < (2); ++k1)
        for (int k2 = 0; k2 < (2); ++k2)
          if (dp[j][k1][k2] != -INF)
            for (int k3 = 0; k3 < (2); ++k3)
              dp[j + 1][k2][k3] =
                  max(dp[j + 1][k2][k3],
                      dp[j][k1][k2] + sum[i] * (pre[k1] + pro[k2] + nxt[k3]));
    }
    if (K == 2) {
      for (int j = 0; j < (2); ++j) {
        an = max(an, max(mi * pre[j], ma * pre[j]) + sum[i] * pro[j] +
                         max(back_mi[i + 1] * nxt[j], back_ma[i + 1] * nxt[j]));
      }
    }
    for (int k1 = 0; k1 < (2); ++k1)
      for (int k2 = 0; k2 < (2); ++k2) {
        dp[1][k1][k2] = max(dp[1][k1][k2], sum[i] * (pro[k1] + nxt[k2]) +
                                               max(mi * nxt[k1], ma * nxt[k1]));
      }
    mi = min(mi, sum[i]);
    ma = max(ma, sum[i]);
  }
  printf("%d\n", an);
  return 0;
}
