Tìm mảng con tổng lớn nhất với độ dài không vượt quá m trong C++

Mô tả vấn đề

Cho n mảng con có độ dài khác nhau. Nhiệm vụ: chọn các mảng con từ các mảng đã cho sao cho tổng độ dài ≤ m và tổng giá trị lớn nhất.

Ví dụ minh họa

Đầu vào:

n = 3, m = 4
arrOfArr[][] = {
    {5, 2, -1, 4, -3},
    {3, -2, 1, 6},
    {-2, 0, 5}
}

Đầu ra:

20

Giải thích:

Chọn: {5,4} từ mảng 1 (độ dài 2), {6} từ mảng 2 (độ dài 1), {5} từ mảng 3 (độ dài 1)
Tổng độ dài = 4, Tổng giá trị = 5+4+6+5 = 20

Phương pháp giải quyết

Sử dụng Quy hoạch động (Dynamic Programming):

1. Với mỗi mảng con, tính trước tổng tiền tố (prefix sum) để lấy tổng bất kỳ đoạn con nào O(1).
2. Với mỗi mảng, tính best[len] = tổng lớn nhất của đoạn con độ dài len (1 ≤ len ≤ min(độ_dài_mảng, m)).
3. DP chính: dp[i][j] = tổng lớn nhất dùng i mảng đầu tiên với tổng độ dài j.

   dp[i][j] = max(dp[i-1][j], dp[i-1][j-cur] + best_i[cur])  với 1 ≤ cur ≤ min(len_i, j)

4. Kết quả là max của hàng cuối cùng dp[n][0...m].

Chương trình minh họa

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

#define MAX_N 5

int findMax(int a, int b) { return (a > b) ? a : b; }

int findMaxSumArray(int arr[][MAX_N], int M) {
    int DP[MAX_N][M+1];
    int sumArray[MAX_N];
    int best[MAX_N];
    memset(DP, -1, sizeof(DP));
    DP[0][0] = 0;

    for (int i = 1; i <= 3; i++) {
        int len = arr[i-1][0]; // giả sử arr[i][0] lưu độ dài
        // Tính prefix sum
        sumArray[0] = 0;
        for (int j = 1; j <= len; j++)
            sumArray[j] = sumArray[j-1] + arr[i-1][j];
        
        // Tính best[len] cho mảng i
        for (int j = 1; j <= len && j <= M; j++) {
            best[j] = -100;
            for (int k = 1; k <= len - j + 1; k++)
                best[j] = findMax(best[j], sumArray[k+j-1] - sumArray[k-1]);
        }

        // DP chuyển trạng thái
        for (int j = 0; j <= M; j++)
            DP[i][j] = DP[i-1][j];
        for (int j = 1; j <= M; j++)
            for (int cur = 1; cur <= j && cur <= len; cur++)
                if (DP[i-1][j-cur] != -1)
                    DP[i][j] = findMax(DP[i][j], DP[i-1][j-cur] + best[cur]);
    }

    int maxSum = 0;
    for (int i = 0; i <= M; i++)
        maxSum = findMax(maxSum, DP[3][i]);
    return maxSum;
}

int main() {
    int arr[][MAX_N] = {
        {3, 2, -1, 6},
        {2, 7, -1},
        {3, 2, 2, -4}
    };
    int m = 4;
    cout << "Tổng lớn nhất độ dài ≤ " << m << " : " << findMaxSumArray(arr, m);
    return 0;
}

Kết quả đầu ra

Tổng lớn nhất độ dài ≤ 4 : 15