Subtask 1. có tối đa một vị trí ~a_i < 0~

Với subtask này, dãy được chia làm ba phần:

• Từ ~a_1~ tới ~a_{i - 1}~ có tổng không âm.
• ~a_i~ có tổng âm.
• Từ ~a_{i + 1}~ tới ~a_n~ có tổng không âm.

Nếu ~K \ge 2~, đương nhiên đáp án là tổng cả dãy, trừ đi phần tử âm đó.

Nếu ~K = 1~, ta có thể chọn phần đầu tiên, phần thứ ba, hoặc cả dãy.

Độ phức tạp: ~O~ (~n~).

Subtask 2. ~k = 1~

Đây là bài toán tìm dãy con có tổng lớn nhất. Bài toán này đã khá quen thuộc, có thể giải bằng mảng cộng dồn.

Độ phức tạp: ~O~ (~n~).

Subtask 3 + 4. ~n, k \le 300~

Ta sẽ quy hoạch động.

Gọi ~f[i][j]~ là tổng lớn nhất khi ta đã chọn ~i~ dãy con, và dãy con cuối cùng đang kết thúc tại ~j~.

Ta có công thức truy hồi: ~f[i][j] = max (f[i - 1][k] + ps[i] - ps[l])~, với ~ps[i]~ là mảng cộng dồn, ~1 \le k < i~ và ~k \le l < i~.

~-ps[j]~ thể hiện ta chọn đoạn con ~[l, i]~.

Độ phức tạp: ~O~ (~n^3~).

Subtask 5. ~n, k \le 2000~

Ta sử dụng prefix min để tối ưu công thức quy hoạch động trên.

Độ phức tạp: ~O~ (~n^2~).

Code mẫu:

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6 + 9;

int n, a[N], k;

namespace sub1 {
    bool valid() {
        int ret = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] < 0) ++ret;
        }
        return ret <= 1;
    }

    void solve() {
        int sum1 = 0, sum2 = 0;
        bool ok = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] < 0) {
                ok = 1; 
                continue;
            }
            if (!ok) sum1 += a[i];
            if (ok) sum2 += a[i];
        }
        if (k == 1) {
            cout << max(sum1, sum2);
        }
        else cout << sum1 + sum2;
        exit(0);
    }
}

namespace sub2 {
    bool valid() {
        return k == 1;
    }

    void solve() {
        int mx = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            mx = max(mx + a[i], a[i]);
            ans = max(ans, mx);
        }
        cout << ans;
        exit(0);
    }
}

namespace subfull {
    int pfs[2002];
    int dp[2002][2002];
    int prefix[2002];

    void solve() {
        for (int i = 1; i <= n; i++) {
            pfs[i] = pfs[i - 1] + a[i];
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = max(dp[i - 1][j], prefix[j - 1] + pfs[i]);
            }
            for (int j = 0; j <= k; j++) {
                prefix[j] = max(prefix[j], dp[i][j] - pfs[i]);
            }
        }
        cout << dp[n][k];
        exit(0);
    }
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//  freopen("phatqua.inp", "r", stdin);
//  freopen("phatqua.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (sub1::valid()) sub1::solve();
    if (sub2::valid()) sub2::solve();
    subfull::solve();
    return 0;
}

// <33