題目描述: 給定一個整數陣列 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) 查詢。
時間複雜度: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)。適合作為通用解法模板。