Constrained Subsequence Sum trong C++

Cho mảng nums và số k, tìm tổng lớn nhất của dãy con không rỗng sao cho với 2 phần tử liên tiếp trong dãy con tại vị trí i < j thì j - i ≤ k.

Ví dụ: [10,2,-9,5,19], k=2 → dãy con [10,2,5,19] tổng = 36.

Giải thuật (DP + Deque tối ưu)

DP[i] = max sum dãy con kết thúc tại i. DP[i] = nums[i] + max(0, max{DP[j] | i-k ≤ j < i}). Dùng deque giảm dần để lấy max trong cửa sổ trượt O(1).

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10;

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp = nums;
        deque<int> dq; // lưu index, dp giảm dần
        dq.push_back(0);
        int ans = nums[0];
        
        for (int i = 1; i < n; i++) {
            // loại bỏ index ngoài cửa sổ [i-k, i-1]
            if (!dq.empty() && dq.front() < i - k) dq.pop_front();
            
            dp[i] = max(dp[i], nums[i] + (dq.empty() ? 0 : dp[dq.front()]));
            ans = max(ans, dp[i]);
            
            // duy trì deque giảm dần theo dp
            while (!dq.empty() && dp[dq.back()] <= dp[i]) dq.pop_back();
            dq.push_back(i);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {10,2,-9,5,19};
    cout << ob.constrainedSubsetSum(v, 2); // 36
    return 0;
}

Đầu vào / Đầu ra

Input: {10,2,-9,5,19}, 2
Output: 36