Chia mảng để tổng lớn nhất nhỏ nhất trong C++

Cho mảng số nguyên dương và số m. Chia mảng thành m mảng con liên tiếp sao cho tổng lớn nhất trong các mảng con là nhỏ nhất có thể.

Ví dụ

nums = [7,2,4,10,9], m = 2

Chia: [7,2,4] (tổng 13) và [10,9] (tổng 19) → max = 19.

Đây là giá trị nhỏ nhất có thể đạt được.

Thuật toán: Quy hoạch động (DP)

dp[i][j] = tổng lớn nhất nhỏ nhất khi chia j phần tử đầu thành i mảng con.

• Tiền tính mảng prefix sum sum[i] = tổng j phần tử đầu.
• Khởi tạo: dp[1][j] = sum[j] (1 mảng con = toàn bộ).
• Chuyển trạng thái: dp[i][j] = min_{k < j} ( max(dp[i-1][k], sum[j] - sum[k]) ).

Lưu ý: Code mẫu dùng cách triển khai khác một chút (tối ưu không gian) nhưng bản chất tương tự.

Cài đặt 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<long long> 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);
    return 0;
}

Độ phức tạp

• Thời gian: O(m * n^2) — 3 vòng lặp lồng.
• Không gian: O(n) — mảng dp và sum.

Tối ưu: Có thể dùng Binary Search trên đáp án + kiểm tra tham lam → O(n log(sum)).

Input / Output

Input:  [7,2,4,10,9] 2
Output: 19