โปรแกรมหาผลรวมสูงสุดของ k สับลิสต์ไม่ทับซ้อนใน C++

ให้ nums และ k หา k สับลิสต์ (subarrays) ไม่ทับซ้อน ผลรวมของผลรวมแต่ละสับลิสต์ มากที่สุด

ตัวอย่าง: nums=[11,-1,2,1,6,-24,11,-9,6], k=3 → 36 เลือก [11,-1,2,1,6] (19), [11] (11), [6] (6) รวม 36

ขั้นตอนการแก้ปัญหา (DP)

1. hi[i] = ผลรวมสูงสุดของ i สับลิสต์ที่จบแล้ว (closed)
2. open[i] = ผลรวมสูงสุดของ i สับลิสต์ ที่สับลิสต์สุดท้ายยังเปิดอยู่ (กำลังขยาย)
3. เริ่ม hi[0]=0, open[1..k]=-inf
4. วนแต่ละ num:
   • nopen[i] = max(open[i]+num, hi[i-1]+num) // ขยายหรือเริ่มใหม่
   • อัปเดต open = nopen
   • hi[i] = max(hi[i], open[i]) // ปิดสับลิสต์ได้
5. คำตอบ = hi[k]

ตัวอย่างโค้ด 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};
    cout << solve(v, 3); // 36
    return 0;
}

อินพุต

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

เอาต์พุต

36