Constrained Subsequence Sum: ผลรวมลำดับย่อยสูงสุดภายใต้เงื่อนไขระยะห่างใน C++

ปัญหา

กำหนดอาร์เรย์ nums และจำนวนเต็ม k หาผลรวมสูงสุดของ Non-empty Subsequence ที่สำหรับคู่ติดกันใดๆ ในลำดับย่อย nums[i], nums[j] (โดย i < j) ต้องมี j - i <= k

ตัวอย่าง: nums = [10,2,-9,5,19], k = 2 → คำตอบ = 36 (ลำดับย่อย: [10, 2, 5, 19])

แนวคิด: DP + Monotonic Deque (Sliding Window Maximum)

DP Definition

dp[i] = ผลรวมสูงสุดของลำดับย่อยที่ ลงท้ายที่ index i (ต้องรวม nums[i])

Recurrence

dp[i] = nums[i] + max(0, max{dp[j] | i-k <= j < i})

คือ เราสามารถต่อจาก dp[j] ในช่วงก่อนหน้าสูงสุด k ตำแหน่ง หรือเริ่มใหม่ที่ i (เทียบเท่า max กับ 0)

เพิ่มประสิทธิภาพด้วย Deque

ต้องการหา max{dp[j]} ใน Sliding Window ขนาด k → ใช้ Monotonic Deque เก็บค่า dp เรียงจากมากไปน้อย

Deque เก็บค่า dp (ไม่ใช่ index) เรียงลำดับมากไปน้อย
ก่อนคำนวณ dp[i]: ลบค่าหน้าสุดถ้าออกนอก window (i > k และ front == dp[i-k-1])
dp[i] = nums[i] + max(0, dq.front())
Push dp[i] เข้า deque: ลบค่าท้ายสุดที่ < dp[i] แล้ว push_back

โค้ด 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.begin(), nums.end());
        deque<int> dq;
        
        dq.push_back(nums[0]);
        int ret = nums[0];
        
        for (int i = 1; i < n; i++) {
            // ลบค่าที่ออกนอก window (ระยะ > k)
            if (i > k && dq.front() == dp[i - k - 1]) {
                dq.pop_front();
            }
            
            // คำนวณ dp[i]
            int best_prev = dq.empty() ? 0 : dq.front();
            dp[i] = max(dp[i], nums[i] + best_prev);
            
            // รักษา Monotonic Deque (มากไปน้อย)
            while (!dq.empty() && dq.back() < dp[i]) {
                dq.pop_back();
            }
            dq.push_back(dp[i]);
            
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};

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

การเดินตัวอย่าง

i	nums[i]	Window (dp)	max_prev	dp[i]	Deque
0	10	-	0	10	[10]
1	2	[10]	10	12	[12, 10]
2	-9	[10,12]	12	3	[12, 10, 3]
3	5	[12,3]	12	17	[17, 12]
4	19	[17,12]	17	36	[36, 17]

ความซับซ้อน

Time: O(n) - แต่ละ element เข้า/ออก deque สูงสุด 1 ครั้ง
Space: O(n) สำหรับ dp array + O(k) สำหรับ deque

Input / Output

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