หาผลรวมสูงสุดของอาร์เรย์ย่อยที่ความยาวรวมไม่เกิน m ใน C++

คำอธิบายปัญหา

ได้รับ n อาร์เรย์ ที่มีความยาวต่างกัน ต้องการเลือก ซับอาร์เรย์ (Subarray) จากแต่ละอาร์เรย์ (อาจเลือกหลายชุดจากอาร์เรย์เดียวกันได้) เพื่อให้:

1. ความยาวรวมของซับอาร์เรย์ที่เลือก ≤ m
2. ผลรวมของสมาชิกในซับอาร์เรย์ที่เลือกเป็นสูงสุด

ตัวอย่าง

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

Output: 20

คำอธิบาย: เลือกซับอาร์เรย์: {5, 4} (จากอาร์เรย์ 1, ความยาว 2), {6} (จากอาร์เรย์ 2, ความยาว 1), {5} (จากอาร์เรย์ 3, ความยาว 1) → ความยาวรวม = 4, ผลรวม = 5+4+6+5 = 20

แนวทางแก้ปัญหา: Dynamic Programming

เป็นปัญหาแบบ Knapsack แบบปรับเปลี่ยน ใช้ DP 2 มิติ:

• DP[i][j] = ผลรวมสูงสุดที่ได้จากอาร์เรย์ 1 ถึง i โดยใช้ความยาวรวม j
• สำหรับแต่ละอาร์เรย์ คำนวณ ผลรวมสูงสุดของซับอาร์เรย์แต่ละความยาว ใส่ในอาร์เรย์ sum[len]
• Transition: DP[i][j] = max(DP[i-1][j], DP[i-1][j-cur] + sum[cur]) สำหรับทุก cur ที่เป็นไปได้

โค้ดตัวอย่าง C++

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

#define N 5

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

int findMaxSumArray(int arr[][N], int M) {
    int DP[N][M];
    int sumArray[M];
    int sum[M];
    
    memset(DP, -1, sizeof(DP[0][0]) * N * M);
    sumArray[0] = 0;
    DP[0][0] = 0;
    
    for (int i = 1; i <= 5; i++) {
        int len = arr[i - 1][0];
        for (int j = 1; j <= len; j++) {
            sumArray[j] = arr[i - 1][j];
            sumArray[j] += sumArray[j - 1];
            sum[j] = -100;
        }
        
        for (int j = 1; j <= len && j <= 6; j++)
            for (int k = 1; k <= len; k++)
                if (j + k - 1 <= len)
                    sum[j] = findMax(sum[j], sumArray[j + k - 1] - sumArray[k - 1]);
        
        for (int j = 0; j <= 6; j++)
            DP[i][j] = DP[i - 1][j];
        
        for (int j = 1; j <= 6; j++)
            for (int cur = 1; cur <= j && cur <= len; cur++)
                DP[i][j] = findMax(DP[i][j], DP[i - 1][j - cur] + sum[cur]);
    }
    
    int maxSum = 0;
    for (int i = 0; i <= 6; i++)
        maxSum = findMax(maxSum, DP[5][i]);
    
    return maxSum;
}

int main() {
    int arr[][N] = { { 3, 2, -1, 6 }, { 2, 7, -1 }, { 3, 2, 2, -4 } };
    int m = 4;
    cout << "Maximum sum array of length less than or equal to " << m << " : " << findMaxSumArray(arr, m);
    return 0;
}

ผลลัพธ์

Maximum sum array of length less than or equal to 4 : 15

หมายเหตุ:

โค้ดตัวอย่างมีค่าคงที่บางส่วน (เช่น 5, 6) ที่อาจต้องปรับตามขนาดอินพุตจริง