C++ में प्रतिबंधित सबसीक्वेंस योग

समस्या विवरण

मान लीजिए हमारे पास nums नामक एक सरणी और एक पूर्णांक k है, हमें उस सरणी के एक गैर-खाली सबसीक्वेंस का अधिकतम योग ज्ञात करना है जैसे कि सबसीक्वेंस में हर दो लगातार संख्याओं nums[i] और nums[j] के लिए, जहां i < j, शर्त j - i <= k सत्य है।

जैसा कि हम जानते हैं, एक सरणी का सबसीक्वेंस सरणी से कुछ तत्वों को हटाकर प्राप्त किया जाता है, शेष तत्वों को उनके मूल क्रम में छोड़कर।

उदाहरण

यदि इनपुट है: [10,2,-9,5,19] और k = 2, तो आउटपुट होगा 36 क्योंकि सबसीक्वेंस है [10,2,5,19]।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (स्लाइडिंग विंडो मैक्सिमम के साथ DP):

ret := -inf
dp नामक एक सरणी परिभाषित करें और दी गई सरणी को इसमें कॉपी करें
एक डीक्यू dq परिभाषित करें
v[0] को dq की शुरुआत में डालें
n := v का आकार
ret := v[0]
i := 1 से आरंभ करें, जब i < n, i को 1 से बढ़ाते हुए:
- यदि i > k और dq का पहला तत्व, dp[i - k - 1] के समान है:
  - dq से फ्रंट तत्व हटाएं
- dp[i] := dp[i] का अधिकतम और (यदि dq खाली है तो dp[i] + 0, अन्यथा dp[i] + dq का पहला तत्व)
- जब (dq खाली नहीं है और dq का अंतिम तत्व < dp[i]):
  - dq से अंतिम तत्व हटाएं
- dp[i] को dq के अंत में डालें
- ret := ret और dp[i] का अधिकतम
ret लौटाएं

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 10;

class Solution {
public:
    int constrainedSubsetSum(vector<int>& v, int k) {
        int ret = -inf;
        vector<int> dp(v.begin(), v.end());
        deque<int> dq;
        dq.push_front(v[0]);
        int n = v.size();
        ret = v[0];
        for (int i = 1; i < n; i++) {
            if (i > k && dq.front() == dp[i - k - 1])
                dq.pop_front();
            dp[i] = max(dp[i], dq.empty() ? dp[i] + 0 : dp[i] + dq.front());
            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));
    return 0;
}

इनपुट

{10,2,-9,5,19}, 2