HardRating 2032

1425. Constrained Subsequence Sum

arraydynamic-programmingqueuesliding-windowheap-priority-queuemonotonic-queue

解題說明

Constrained Subsequence Sum

題目描述：給定一個整數陣列 nums 和一個整數 k。找出一個子序列的最大元素和，使得子序列中任意兩個相鄰元素在原陣列中的索引差不超過 k。

解題思路：定義 dp[i] 為以 nums[i] 結尾的滿足約束的子序列最大和。轉移方程為 dp[i] = nums[i] + max(0, max(dp[j])) 其中 j 在 [i-k, i-1] 範圍內。需要快速查詢滑動窗口中的最大值，使用單調遞減佇列（monotonic deque）來維護窗口最大值，實現 O(1) 查詢。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個元素最多進出佇列一次

空間複雜度：O(n) — dp 陣列和單調佇列

虛擬碼

1. Initialize dp[n], monotonic deque dq, result = -infinity
2. For each index i from 0 to n-1:
   a. Remove indices from front of dq that are outside window [i-k, i-1]
   b. dp[i] = nums[i] + max(0, dp[dq.front()]) if dq is non-empty, else just nums[i]
   c. Remove indices from back of dq where dp[index] <= dp[i]
   d. Push i to back of dq
   e. Update result = max(result, dp[i])
3. Return result

其他解法

方法二：優先佇列（Max Heap） 使用最大堆維護 (dp[j], j) 對。每次取堆頂元素，如果索引不在窗口內就彈出。時間複雜度 O(n log n)，比單調佇列多一個 log 因子。

方法三：線段樹 使用線段樹維護區間最大值查詢。每次查詢 [i-k, i-1] 的最大 dp 值。時間複雜度 O(n log n)，空間 O(n)。適合作為通用解法模板。

延伸思考

如果約束改為「子序列中任意兩個相鄰元素的索引差至少為 k」，解法需要如何改變？
如何推廣到二維情況：在矩陣中找出滿足行列跨度約束的子序列最大和？
單調佇列和滑動窗口最大值（LeetCode 239）有什麼關聯？

Constrained Subsequence Sum — CaffeCode