Tối đa hóa giá trị mảng với giới hạn trên và dưới bằng cách cộng/trừ lần lượt trong C++

Đề bài

Cho mảng arr[], số bắt đầu num, giới hạn trên maxLimit. Duyệt mảng từ đầu, tại mỗi bước được phép cộng hoặc trừ arr[i] vào giá trị hiện tại, miễn là kết quả nằm trong [0, maxLimit]. Tìm giá trị lớn nhất có thể đạt được sau khi duyệt hết mảng.

Ví dụ: arr={3,10,6,4,5}, num=1, maxLimit=15 → 1+3+10-6-4+5 = 9.

Thuật toán (Đệ quy + Memoization / DP)

Trạng thái: dp[idx][val] = có thể đạt được giá trị val sau khi xử lý đến chỉ số idx không.

Khởi tạo dp[0][num] = true. Duyệt i từ 0 đến n-1, với mỗi val có dp[i][val]=true, thử val+arr[i] và val-arr[i] nếu trong khoảng cho phép.

Kết quả: val lớn nhất có dp[n][val]=true.

Ví dụ minh họa (C++)

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

int getMaxValue(int* arr, int n, int num, int maxLimit) {
    vector<vector<bool>> dp(n+1, vector<bool>(maxLimit+1, false));
    dp[0][num] = true;
    for (int i = 0; i < n; ++i) {
        for (int val = 0; val <= maxLimit; ++val) {
            if (!dp[i][val]) continue;
            if (val + arr[i] <= maxLimit) dp[i+1][val + arr[i]] = true;
            if (val >= arr[i]) dp[i+1][val - arr[i]] = true;
        }
    }
    for (int val = maxLimit; val >= 0; --val)
        if (dp[n][val]) return val;
    return -1; // không có giải pháp
}

int main() {
    int arr[] = {3, 10, 6, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int num = 1, maxLimit = 15;
    cout << "Gia tri lon nhat = " << getMaxValue(arr, n, num, maxLimit) << endl;
    return 0;
}

Kết quả

Gia tri lon nhat = 9

Lưu ý: Code gốc dùng đệ quy không memoization (chậm), phiên bản trên dùng DP bottom-up O(n * maxLimit).