#include <bits/stdc++.h>
using namespace std;
int dp[30003][203][2][2][2];
int inf = (int)400000000;
int N, K;
int a[30003];
int s[2] = {1, -1};
int main() {
  scanf("%d%d", &N, &K);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i <= N + 1; ++i) {
    for (int j = 0; j <= K + 1; ++j) {
      for (int e = 0; e < 2; ++e) {
        for (int c1 = 0; c1 < 2; ++c1) {
          for (int c2 = 0; c2 < 2; ++c2) {
            dp[i][j][e][c1][c2] = -inf;
            if (j == 0 && e == 0) {
              dp[i][j][e][c1][c2] = 0;
            }
          }
        }
      }
    }
  }
  int ans = -inf;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= K; ++j) {
      for (int e = 0; e < 2; ++e) {
        for (int c1 = 0; c1 < 2; ++c1) {
          for (int c2 = 0; c2 < 2; ++c2) {
            if (dp[i][j][e][c1][c2] == -inf) continue;
            if (j == 0) {
              dp[i + 1][j + 1][1][c1][c2] =
                  max(dp[i + 1][j + 1][1][c1][c2], s[c2] * a[i + 1]);
            } else if (j <= K - 1) {
              dp[i + 1][j][1][c1][c2] =
                  max(dp[i + 1][j][1][c1][c2],
                      (j == 1 ? 0 : -s[c1] * a[i + 1]) + s[c2] * a[i + 1] +
                          dp[i][j][e][c1][c2]);
              if (e == 0)
                dp[i + 1][j][e][c1][c2] =
                    max(dp[i + 1][j][e][c1][c2], dp[i][j][e][c1][c2]);
              if (e != 0) {
                for (int x = 0; x < 2; ++x) {
                  dp[i + 1][j + 1][0][c2][x] =
                      max(dp[i + 1][j + 1][0][c2][x], dp[i][j][e][c1][c2]);
                  dp[i + 1][j + 1][1][c2][x] = max(
                      dp[i + 1][j + 1][1][c2][x],
                      -s[c2] * a[i + 1] + (j == K - 1 ? 0 : s[x] * a[i + 1]) +
                          dp[i][j][e][c1][c2]);
                }
              }
            } else if (j == K) {
              dp[i + 1][j][1][c1][c2] =
                  max(dp[i + 1][j][1][c1][c2],
                      -s[c1] * a[i + 1] + dp[i][j][e][c1][c2]);
              if (e == 0)
                dp[i + 1][j][e][c1][c2] =
                    max(dp[i + 1][j][e][c1][c2], dp[i][j][e][c1][c2]);
            }
          }
        }
      }
    }
  }
  for (int i = 0; i <= N; ++i) {
    for (int c1 = 0; c1 < 2; ++c1) {
      for (int c2 = 0; c2 < 2; ++c2) {
        ans = max(ans, dp[i][K][1][c1][c2]);
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}
