由 [LeetCode 239. Sliding Window Maximum]的延伸，以dp找到subsequence中出現過sum最大值
定義 : dp[i] = prefix max subsequence sum from 0~i-1 + nums[i]
狀態轉移 : dp[i] = max(0, dp[i-1]) + nums; [1]
if dp[i-1] > 0 選這個
else 重新歸零計算 只抓取 nums[i]
由於題目有限制 subsequence 之間的 index 不能差超過 k
需要將狀態轉移改成如下:
dp[i] = max(dp[i-1], dp[i-1], .... dp[i-k], 0) + nums;
然而因為 k的範圍可以到 10e5，硬幹去找max的最大值的話，整體複雜度會上升至 10e5 * 10e5 (nums.size() * k)
處理的方法有兩種:
1. 用priority_queue抓取目前最大紀錄的dp[i-m], where 1<=m<=k
2. 用 monotonic queue 紀錄最大值，次大值...
monotonic queue如何幫助dp紀錄最大值?
第一，最大值永遠放在最左側，意味著如果有新的value進來，且比queue中所有元素大，全部刪除只留下新的value
如果不是最大值，就從後面開始比較，直到遇到比她還大的；或是queue已經為空(此狀況就是上述提及的最大值) [2]
另外實作中，使用index紀錄
由於monotonic queue會有pop_front(超過k的限制)，以及pop_back(紀錄最大值)，使用dequeue最為適合。
| class Solution { public: int constrainedSubsetSum(vector<int>& nums, int k) { int n = nums.size(); vector<int> dp(n); deque<int> q; int ans = INT_MIN; // 避免nums[i]都是負值 for(int i=0;i<n;i++){ if(!q.empty() && q.front() <= (i-k-1)) // 超過k的限制 q.pop_front(); dp[i] = (q.empty()? 0 : max(dp[q.front()], 0)) + nums[i]; // [1] while(!q.empty() && dp[i] > dp[q.back()]){ // [2] q.pop_back(); } q.push_back(i); ans = max(ans, dp[i]); } return ans; } }; |
