/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;
const int maxn = 3e4 + 10, maxk = 210;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int n, k;
ll a[maxn], dp[maxn][maxk], p[maxn], op[maxn][maxk];

ll cost(int i, int j)
{
    return max(abs((p[j - 1] - p[i - 1]) - a[j]),
               abs((p[j] - p[i]) - a[i]));
}

struct segment_tree
{
    ll tree[4 * maxn], lazy[4 * maxn];

    void push_lazy(int root, int left, int right)
    {
        tree[root] += lazy[root];
        if (left != right)
        {
            lazy[root * 2] += lazy[root];
            lazy[root * 2 + 1] += lazy[root];
        }
        lazy[root] = 0;
    }

    void point_update(int root, int left, int right, int idx, ll val)
    {
        push_lazy(root, left, right);
        if (left == right)
        {
            tree[root] = val;
            return;
        }

        int mid = (left + right) / 2;
        if (idx <= mid)
            point_update(root * 2, left, mid, idx, val);
        else
            point_update(root * 2 + 1, mid + 1, right, idx, val);

        tree[root] = tree[root * 2];
        if (tree[root * 2 + 1] > tree[root])
            tree[root] = tree[root * 2 + 1];
    }

    void range_update(int root, int left, int right, int qleft, int qright, ll val)
    {
        push_lazy(root, left, right);

        if (left == qleft && right == qright)
        {
            lazy[root] += val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        if (qright <= mid)
            range_update(root * 2, left, mid, qleft, qright, val);
        else if (qleft > mid)
            range_update(root * 2 + 1, mid + 1, right, qleft, qright, val);
        else
        {
            range_update(root * 2, left, mid, qleft, mid, val);
            range_update(root * 2 + 1, mid + 1, right, mid + 1, qright, val);
        }
        push_lazy(root * 2, left, mid);
        push_lazy(root * 2 + 1, mid + 1, right);
                tree[root] = tree[root * 2];
        if (tree[root * 2 + 1] > tree[root])
            tree[root] = tree[root * 2 + 1];
    }

    ll query(int root, int left, int right, int qleft, int qright)
    {
        push_lazy(root, left, right);

        if (left == qleft && right == qright)
            return tree[root];
        int mid = (left + right) / 2;

        if (qright <= mid)
            return query(root * 2, left, mid, qleft, qright);
        if (qleft > mid)
            return query(root * 2 + 1, mid + 1, right, qleft, qright);

        return max(query(root * 2, left, mid, qleft, mid),
                   query(root * 2 + 1, mid + 1, right, mid + 1, qright));
    }
};


segment_tree st[maxk * 2];

void solve()
{
    cin >> n >> k;
    bool tf = false;
    if (k % 2 == 0)
        tf = true;
    k /= 2;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }

    for (int i = 2; i <= n; i ++)
        dp[i][1] = cost(1, i);
    dp[0][1] = dp[1][1] = -1e18;
    for (int j = 2; j <= k; j ++)
    {
        dp[0][j] = -1e18;
        st[j * 2].point_update(1, 0, n, 0, -1e18);
        for (int i = 1; i <= n; i ++)
        {
            dp[i][j] = st[j * 2].query(1, 0, n, 0, i - 1) + a[i];
            st[j * 2].range_update(1, 0, n, 0, i - 1, a[i]);
            st[j* 2].point_update(1, 0, n, i, dp[i - 1][j - 1] - a[i]);

        }
        st[j * 2 + 1].point_update(1, 0, n, 0, -1e18);
        for (int i = 1; i <= n; i ++)
        {
            dp[i][j] = max(dp[i][j],
                           st[j * 2 + 1].query(1, 0, n, 0, i - 1) - a[i]);
            st[j * 2 + 1].range_update(1, 0, n, 0, i - 1, a[i]);
            st[j * 2 + 1].point_update(1, 0, n, i, dp[i - 1][j - 1] + a[i]);
        }

    }



    cout << dp[n][k] << endl;



}

int main()
{
    freopen("monkeys.in", "r", stdin);
    freopen("monkeys.out", "w", stdout);
    ///speed();
    solve();

    return 0;
}
/**
10 7
1 2 3 4 5 6 7 8 9 10
15 6
7 2 4 9 10 4 5 5 7 1 7 7 2 9 5
*/