#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
int n, npart;
int x[30000];
int f[2][201][2];
int g[2][200][2][2];
void run() {
  scanf("%d%d", &n, &npart);
  for (int i = (0); i < (n); ++i) scanf("%d", &x[i]);
  int at = 0;
  for (int i = (0); i <= (npart); ++i)
    for (int op = (0); op < (2); ++op) f[at][i][op] = i == 0 ? 0 : INT_MIN;
  for (int i = (0); i < (npart); ++i)
    for (int op1 = (0); op1 < (2); ++op1)
      for (int op2 = (0); op2 < (2); ++op2) g[at][i][op1][op2] = INT_MIN;
  for (int j = (0); j < (n); ++j) {
    int to = 1 - at;
    for (int i = (0); i <= (npart); ++i)
      for (int op = (0); op < (2); ++op) f[to][i][op] = INT_MIN;
    for (int i = (0); i < (npart); ++i)
      for (int op1 = (0); op1 < (2); ++op1)
        for (int op2 = (0); op2 < (2); ++op2) g[to][i][op1][op2] = INT_MIN;
    for (int i = (0); i <= (npart); ++i)
      for (int op = (0); op < (2); ++op)
        if (f[at][i][op] != INT_MIN) {
          if ((f[at][i][op]) >= f[to][i][op]) f[to][i][op] = (f[at][i][op]);
          ;
          if (i != npart)
            for (int op2 = (0); op2 < (2); ++op2)
              if ((f[at][i][op] +
                   (i == 0        ? 0
                    : 1 - op == 0 ? -x[j]
                                  : +x[j]) +
                   (i == npart - 1 ? 0
                    : op2 == 0     ? -x[j]
                                   : +x[j])) >= g[to][i][1 - op][op2])
                g[to][i][1 - op][op2] = (f[at][i][op] +
                                         (i == 0        ? 0
                                          : 1 - op == 0 ? -x[j]
                                                        : +x[j]) +
                                         (i == npart - 1 ? 0
                                          : op2 == 0     ? -x[j]
                                                         : +x[j]));
          ;
        }
    for (int i = (0); i < (npart); ++i)
      for (int op1 = (0); op1 < (2); ++op1)
        for (int op2 = (0); op2 < (2); ++op2)
          if (g[at][i][op1][op2] != INT_MIN) {
            if ((g[at][i][op1][op2] +
                 (i == 0     ? 0
                  : op1 == 0 ? -x[j]
                             : +x[j]) +
                 (i == npart - 1 ? 0
                  : op2 == 0     ? -x[j]
                                 : +x[j])) >= g[to][i][op1][op2])
              g[to][i][op1][op2] = (g[at][i][op1][op2] +
                                    (i == 0     ? 0
                                     : op1 == 0 ? -x[j]
                                                : +x[j]) +
                                    (i == npart - 1 ? 0
                                     : op2 == 0     ? -x[j]
                                                    : +x[j]));
            ;
          }
    for (int i = (0); i < (npart); ++i)
      for (int op1 = (0); op1 < (2); ++op1)
        for (int op2 = (0); op2 < (2); ++op2)
          if (g[to][i][op1][op2] != INT_MIN) {
            if ((g[to][i][op1][op2]) >= f[to][i + 1][op2])
              f[to][i + 1][op2] = (g[to][i][op1][op2]);
            ;
          }
    at = to;
  }
  int ret = INT_MIN;
  for (int op = (0); op < (2); ++op)
    if ((f[at][npart][op]) >= ret) ret = (f[at][npart][op]);
  ;
  printf("%d\n", ret);
}
int main() {
  run();
  return 0;
}
