#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
long long n, k;
long long a[300005];
long long dp[2][305][2][3][3];
signed main() {
  cin >> n >> k;
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (long long pos = 0; pos <= 1; pos++) {
    for (long long num = 0; num <= k; num++) {
      for (long long completed = 0; completed <= 1; completed++) {
        for (long long prev = 0; prev <= 2; prev++) {
          for (long long next = 0; next <= 2; next++) {
            dp[pos][num][completed][prev][next] = -1e15;
          }
        }
      }
    }
  }
  dp[0][0][1][0][1] = 0;
  for (long long pos = 0; pos <= n; pos++) {
    for (long long num = 0; num <= k; num++) {
      for (long long completed = 0; completed <= 1; completed++) {
        for (long long prev = 0; prev <= 2; prev++) {
          for (long long next = 0; next <= 2; next++) {
            if (dp[0][num][completed][prev][next] == -1e15) continue;
            if (pos < n && completed)
              dp[1][num][completed][prev][next] =
                  max(dp[1][num][completed][prev][next],
                      dp[0][num][completed][prev][next]);
            if (pos < n && !completed && num > 0)
              dp[1][num][completed][prev][next] =
                  max(dp[1][num][completed][prev][next],
                      dp[0][num][completed][prev][next] +
                          (prev + next - 2) * a[pos + 1]);
            if (pos > 0 && num > 0 && !completed)
              dp[0][num][true][prev][next] = max(dp[0][num][true][prev][next],
                                                 dp[0][num][false][prev][next]);
            if (pos < n && completed && num < k) {
              for (long long next2 = 0; next2 <= 2; next2++) {
                if (num == k - 1 && (next2 == 0 || next2 == 2)) continue;
                if (num != k - 1 && next2 == 1) continue;
                dp[1][num + 1][false][2 - next][next2] =
                    max(dp[1][num + 1][false][2 - next][next2],
                        dp[0][num][completed][prev][next] +
                            (-next + next2) * a[pos + 1]);
              }
            }
          }
        }
      }
    }
    if (pos == n) {
      cout << max(dp[0][k][1][0][1], dp[0][k][1][2][1]);
      return 0;
    }
    for (long long num = 0; num <= k; num++) {
      for (long long completed = 0; completed <= 1; completed++) {
        for (long long prev = 0; prev <= 2; prev++) {
          for (long long next = 0; next <= 2; next++) {
            dp[0][num][completed][prev][next] =
                dp[1][num][completed][prev][next];
            dp[1][num][completed][prev][next] = -1e15;
          }
        }
      }
    }
  }
}
