Với ~N \leq 1000~:

• Gọi ~dp[k][i]~ là tổng điểm lớn nhất đạt được khi xét tới phần tử thứ ~i~ cắt được ~k~ đoạn.

• Ta có công thức quy hoạch động: $$dp[k][i] = max_{j=1}^{i-1}(dp[k-1][j] + max_{t=j}^i a_t + min_{t=j}^i a_t)$$

Với ~N \leq 10^5~:

• Ta cần tối ưu lần duyệt ~j~ ở công thức quy hoạch động trên.

• Khi xét tới phần tử thứ ~i~:

  • ~dmax[j]~ là lượng thay đổi khi đi từ phần tử ~j + 1~ về ~j~ của trạng thái cực đại hóa.

  • ~dmin[j]~ là lượng thay đổi khi đi từ phần tử ~j + 1~ về ~j~ của trạng thái cực tiểu hóa.

Ví dụ:

Cho ~a = [3, 5, 2, 3, 4]~

• Khi xét tới phần tử thứ 2:

  • ~dmax = [0, 0, 0, 0, 0]~, ~dmin = [-2, 0, 0, 0, 0]~

• Khi xét tới phần tử thứ 3:

  • ~dmax = [0, 3, 0, 0, 0]~, ~dmin = [0, 0, 0, 0, 0]~

• Khi xét tới phần tử thứ 4:

  • ~dmax = [0, 3, 0, 0, 0]~, ~dmin = [0, 0, -1, 0, 0]~

• Khi xét tới phần tử thứ 5:

  • ~dmax = [0, 1, 0, 0, 0]~, ~dmin = [0, 0, -1, -1, 0]~

Công thức lúc này sẽ là: $$dp[k][i] = max_{j=1}^{i-1}(dp[k-1][j] + \sum_{t = j}^i dmax_t + \sum_{t = j}^i dmin_t)$$

Để xác định nhanh mảng ~dmax~, ~dmin~ cũng như truy xuất nhanh vị trí để đạt giá trị lớn nhất, ta sẽ sử dụng segment tree.

#include <bits/stdc++.h> // QioCas

using namespace std; 
using ll = long long;

#ifdef LOCAL
#include </mnt/d/Cp/Lib/debug.h>
#else
#define print(...) void(000) /* ignore */
#define debug(...) void(000) /* ignore */
#endif

const int N = 200200;

int n, k, a[N];
ll dp[21][N];

ll val[N][3];

int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

int logn = 0, sz = 0;
struct Node { ll suffix = -1e18, sum = 0; } IT[500500];

Node operator + (Node u, Node v) {
    return Node{max(v.suffix, v.sum + u.suffix), u.sum + v.sum};
}

void build() {
    logn = ceil_pow2(n);
    sz = 1 << logn;

    for(int i = 1; i <= n; ++i) {
        val[i][0] = -1e18;
        val[i][1] = val[i][2] = 0;
        IT[sz + i - 1] = Node{val[i][0], 0};
    }
    for(int i = sz - 1; i > 0; --i) {
        IT[i] = IT[i << 1] + IT[i << 1 | 1];
    }
}

void update(int u, int type, ll x) {
    val[u][type] = x;
    IT[sz + u - 1] = {val[u][0] + val[u][1] + val[u][2], val[u][1] + val[u][2]};
    for(u += sz - 1; (u >>= 1) > 0; ) {
        IT[u] = IT[u << 1] + IT[u << 1 | 1];
    }
}

Node prod(int l, int r) {
    Node resL = Node{}, resR = Node{};
    for(l += sz - 1, r += sz; l < r; l >>= 1, r >>= 1) {
        if(l & 1) resL = resL + IT[l++];
        if(r & 1) resR = IT[--r] + resR;
    }
    return resL + resR;
}

signed main() {
    freopen("maximize.inp", "r", stdin);
    freopen("maximize.out", "w", stdout);

    cin.tie(NULL)->sync_with_stdio(false);
    debug(file());

    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    fill(&dp[0][0], &dp[21 - 1][N - 1] + 1, -1e18);

    dp[0][0] = 0;

    for(int x = 1; x <= k; ++x) {
        stack<int> minq, maxq;
        minq.push(0); maxq.push(0);
        build();
        for(int i = 1; i <= n; ++i) {
            update(i, 0, dp[x - 1][i - 1]);

            while(maxq.size() > 1 && a[maxq.top()] <= a[i]) {
                update(maxq.top(), 1, 0);
                maxq.pop();
            }

            while(minq.size() > 1 && a[minq.top()] >= a[i]) {
                update(minq.top(), 2, 0);
                minq.pop();
            }
            if(maxq.top() != 0) update(maxq.top(), 1, a[maxq.top()] - a[i]);
            if(minq.top() != 0) update(minq.top(), 2, a[minq.top()] - a[i]);
            dp[x][i] = prod(1, n).suffix + 2ll * a[i];

            minq.push(i);
            maxq.push(i);
        }
    }
    cout << dp[k][n];
}