Chương trình tìm tổng lớn nhất của k dãy con không giao nhau trong C++

Mô tả bài toán

Cho mảng nums và số k. Chọn k dãy con không giao nhau, không rỗng sao cho tổng của các tổng dãy con là lớn nhất.

Ví dụ: nums = [11,-1,2,1,6,-24,11,-9,6], k=3 → 36 (chọn [11,-1,2,1,6], [11], [6]).

Giải thuật (Quy hoạch động)

1. hi[i] = tổng lớn nhất dùng i dãy con đã kết thúc.
2. open[i] = tổng lớn nhất dùng i dãy con, dãy thứ i đang mở (chưa kết thúc).
3. Khởi tạo hi[0]=0, các giá trị khác = -INF.
4. Duyệt từng num trong nums:
   • Cập nhật nopen[i] từ open[i] (tiếp tục dãy) và hi[i-1] (bắt đầu dãy mới).
   • Cập nhật hi[i] = max(hi[i], open[i]).
5. Kết quả hi[k].

Ví dụ minh họa (C++)

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

int solve(vector<int>& nums, int k) {
    int n = nums.size();
    if (n == 0 || k == 0) return 0;
    vector<int> hi(k+1, INT_MIN), open(k+1, INT_MIN);
    hi[0] = 0;
    for (int num : nums) {
        vector<int> nopen(k+1, INT_MIN);
        for (int i = 1; i <= k; ++i) {
            if (open[i] > INT_MIN) nopen[i] = open[i] + num;
            if (hi[i-1] > INT_MIN) nopen[i] = max(nopen[i], hi[i-1] + num);
        }
        open = move(nopen);
        for (int i = 1; i <= k; ++i) hi[i] = max(hi[i], open[i]);
    }
    return hi[k];
}

int main() {
    vector<int> v = {11,-1,2,1,6,-24,11,-9,6};
    int k = 3;
    cout << solve(v, 3);
    return 0;
}

Đầu vào

{11,-1,2,1,6,-24,11,-9,6}, 3

Đầu ra

36