C++ में दिए गए अंतर के साथ सबसे लंबा अंकगणितीय सबसीक्वेंस

मान लीजिए हमारे पास एक इंटीजर ऐरे arr और एक इंटीजर difference है, हमें arr में सबसे लंबे सबसीक्वेंस की लंबाई ढूंढनी है जो एक अंकगणितीय अनुक्रम है जैसे कि सबसीक्वेंस में आसन्न एलिमेंट्स के बीच का अंतर difference के समान है। यदि इनपुट [1,5,7,8,5,3,4,2,1] है और difference -2 है, तो आउटपुट 4 होगा, क्योंकि सबसे लंबा अंकगणितीय अनुक्रम [7,5,3,1] है।

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

• एक मैप m परिभाषित करें
• n := ऐरे arr का आकार, ans := 0 सेट करें
• i के लिए 0 से n - 1 तक की रेंज में
  • x := arr[i]
  • m[x] := 1 + m[x - d]
  • ans := ans और m[x] का मैक्स
• ans लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित इम्प्लीमेंटेशन देखें -

#include <bits/stdc++.h> using namespace std; class Solution { public:    int longestSubsequence(vector<int>& arr, int d) {       int n = arr.size();       map <int,int> m;       int ans = 0;       for(int i =0;i<n;i++){          int x = arr[i];          m[x] = 1 + (m[x-d]);          ans = max(ans,m[x]);       }       return ans;    } }; main(){    vector<int> v1 = {1,5,7,8,5,3,4,2,1};    Solution ob;    cout <<ob.longestSubsequence(v1, -2); }

इनपुट

[1,5,7,8,5,3,4,2,1] -2

आउटपुट

4