Subtask 1: ~O(n)~.

Ta chuẩn bị hai mảng ~p_i~ và ~s_i~ lần lượt là đoạn có tổng lớn nhất nếu xét tiền tố và hậu tố tại ~i~. Với ~k = 2~, ta có thể xét vị trí ~1 \le i < n~ và lấy max các ~p_i + s_{i + 1}~.

Subtask 2: ~O(n)~.

Dành cho bạn đọc.

Subtask 3: ~O(n \times k)~.

Ta tính mảng ~dp(i, j, 0/1)~ là tổng lớn nhất nếu xét tiền tố độ dài ~i~, đang chọn được ~j~ dãy và được chọn tiếp dãy thứ ~j~ hay không.

Nếu được chọn tiếp dãy thứ ~j~, ta có ba khả năng là thêm phần tử ~a_{i + 1}~ vào dãy ~j~ hoặc dãy ~j + 1~ hoặc không sử dụng.

Nếu không được chọn tiếp dãy thứ ~j~, ta chỉ còn lại hai khả năng là thêm phần tử ~a_{i + 1}~ vào dãy ~j + 1~ hoặc không sử dụng.

Đáp số: ~max(dp(n, k, 1), dp(n, k, 0))~.

Code mẫu

#include <iostream>
#include<vector>
#include <climits>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k; 
    vector<int> a(n + 1, 0); 
    vector<long long> pref(n + 1, 0); 
    for(int i = 1; i <= n; i++) { 
        cin >> a[i]; 
        pref[i] = pref[i - 1] + a[i]; 
    }

    vector<vector<long long> > dp(k + 1, vector<long long> (n + 1, LLONG_MIN / 100)), maxcombi = dp; 

    for(int j = 0; j <= k; j++) { 
        if(!j) { 
            dp[0][0] = 0; 
        }
        else {
            for(int i = 1; i <= n; i++) { 
                dp[j][i] = maxcombi[j - 1][i - 1] + pref[i]; 
            }
        }

        long long maxdp = maxcombi[j][0] = dp[j][0]; 
        for(int i = 1; i <= n; i++) { 
            maxdp = max(maxdp, dp[j][i]); 
            maxcombi[j][i] = max(maxcombi[j][i - 1], maxdp - pref[i]); 
        }
    }
    long long ans = LLONG_MIN / 100ll; 
    for(int i = 1; i <= n; i++) { 
        ans = max(ans, dp[k][i]);
    }
    cout << ans; 
}