C++ में सबसे लंबा हार्मोनियस सबसीक्वेंस

समस्या विवरण

मान लीजिए हमारे पास एक पूर्णांक सरणी है; हमें इसके सभी संभावित सबसीक्वेंस में से सबसे लंबे हार्मोनियस सबसीक्वेंस की लंबाई ज्ञात करनी है। जैसा कि हम जानते हैं, एक हार्मोनियस अनुक्रम सरणी वह होती है जहां उसका अधिकतम मान और न्यूनतम मान का अंतर ठीक 1 होता है।

उदाहरण

यदि इनपुट है: [1,3,2,2,5,2,3,7], तो आउटपुट होगा 5, क्योंकि सबसे लंबा हार्मोनियस सबसीक्वेंस [2,2,2,3,3] है (अथवा [3,2,2,2,3] आदि)।

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

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें:

एक मैप m परिभाषित करें
प्रत्येक n के लिए nums में:
- m[n] को 1 से बढ़ाएं
प्रत्येक कुंजी-मान जोड़ी (k,v) के लिए m में:
- it := m में (k+1) की स्थिति
- यदि 'it' m में मौजूद है, तो:
  - max_ := max_ और it के मान का अधिकतम
max_ लौटाएं

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

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

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> m;
        for (const int n : nums)
            ++m[n];
        int max_ = 0;
        for (const auto & [k, v] : m) {
            auto it = m.find(k + 1);
            if (it != m.end())
                max_ = max(max_, v + it->second);
        }
        return max_;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,4,3,3,6,3,4,8};
    cout << (ob.findLHS(v));
    return 0;
}

इनपुट

{2,4,3,3,6,3,4,8}