主題

LeetCode 1425. Constrained Subset Sum

Mmry | 2023-10-21 11:48:08 | 巴幣 0 | 人氣 212

由 [LeetCode 239. Sliding Window Maximum]的延伸，以dp找到subsequence中出現(xiàn)過sum最大值

定義 : dp[i] = prefix max subsequence sum from 0~i-1 + nums[i]

狀態(tài)轉移 : dp[i] = max(0, dp[i-1]) + nums; [1]

if dp[i-1] > 0 選這個

else 重新歸零計算只抓取 nums[i]

由於題目有限制 subsequence 之間的 index 不能差超過 k

需要將狀態(tài)轉移改成如下:

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;

    }
};