แบ่งอาเรย์เพื่อให้ผลรวมสูงสุดน้อยที่สุดใน C++

ภาพรวมปัญหา

ให้อาเรย์จำนวนเต็มบวกและจำนวน m แบ่งอาเรย์เป็น m ส่วนย่อยติดต่อกัน (contiguous subarrays) ให้ผลรวมสูงสุดของส่วนย่อยแต่ละส่วนน้อยที่สุด

ตัวอย่าง

nums = [7,2,4,10,9], m = 2
แบ่งเป็น [7,2,4] (sum=13) และ [10,9] (sum=19) → ผลรวมสูงสุด = 19

วิธีแก้ปัญหา: Dynamic Programming

dp[i][j] = ผลรวมสูงสุดน้อยที่สุดเมื่อแบ่งอาเรย์จาก index i ถึงท้าย เป็น j ส่วน

ขั้นตอนหลัก

1. คำนวณ prefix sum: sum[i] = ผลรวม nums[0..i]
2. เริ่มต้น dp[i][1] = sum[n-1] - (i>0?sum[i-1]:0) (แบ่ง 1 ส่วน)
3. สำหรับ parts = 2 ถึง m:
   • สำหรับ start = 0 ถึง n-parts:
     • ลอง end = start+1 ถึง n-parts+1
     • leftSum = sum[end-1] - (start>0?sum[start-1]:0)
     • dp[start][parts] = min(dp[start][parts], max(leftSum, dp[end][parts-1]))
4. คำตอบ = dp[0][m]

โค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int splitArray(vector<int>& v, int m) {
        int n = v.size();
        vector<lli> dp(n), sum(n);
        sum[0] = v[0];
        for (int i = 1; i < n; i++) sum[i] = sum[i-1] + v[i];
        dp[0] = sum[n-1];
        for (int i = 1; i < n; i++) dp[i] = sum[n-1] - sum[i-1];
        for (int i = 1; i < m; i++) {
            for (int start = 0; start < n-i; start++) {
                for (int end = start+1; end <= n-i; end++) {
                    lli leftSum = (start==0 ? sum[end-1] : sum[end-1] - sum[start-1]);
                    dp[start] = min(dp[start], max(leftSum, dp[end]));
                }
            }
        }
        return dp[0];
    }
};

int main() {
    Solution ob;
    vector<int> v = {7,2,4,10,9};
    cout << (ob.splitArray(v, 2));
}

การวิเคราะห์ความซับซ้อน

• เวลา: O(n² × m)
• พื้นที่: O(n)

หมายเหตุ

วิธีนี้เป็น DP แบบ bottom-up สามารถปรับปรุงได้ด้วย Binary Search + Greedy ให้ O(n log sum)