मान लीजिए कि हमारे पास एक पूर्णांक सरणी arr और एक पूर्णांक अंतर है, हमें arr में सबसे लंबे बाद की लंबाई का पता लगाना है जो एक अंकगणितीय अनुक्रम है जैसे कि बाद में आसन्न तत्वों के बीच का अंतर अंतर के समान है। तो अगर इनपुट [1,5,7,8,5,3,4,2,1] जैसा है और अंतर -2 है, तो आउटपुट -4 होगा, क्योंकि सबसे लंबा अंकगणितीय अनुक्रम [7,5 है, 3,1]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- नक्शा परिभाषित करें मी
- n:=सरणी का आकार गिरफ्तारी, सेट उत्तर:=0
- मैं के लिए 0 से n - 1 की सीमा में
- x :=arr[i]
- m[x] :=1 + m[x - d]
- उत्तर :=अधिकतम और m[x]
- वापसी उत्तर
उदाहरण
आइए हम इसे बेहतर ढंग से समझने के लिए निम्नलिखित कार्यान्वयन को देखें -
#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