ধরুন আমাদের একটি পূর্ণসংখ্যা অ্যারে অ্যারে এবং একটি পূর্ণসংখ্যার পার্থক্য আছে, আমাদেরকে অ্যারের সবচেয়ে দীর্ঘতম অনুক্রমের দৈর্ঘ্য খুঁজে বের করতে হবে যা একটি গাণিতিক ক্রম যেমন পরবর্তীতে সন্নিহিত উপাদানগুলির মধ্যে পার্থক্য পার্থক্য হিসাবে একই. সুতরাং যদি ইনপুট হয় [1,5,7,8,5,3,4,2,1] এবং পার্থক্য -2 হয়, তাহলে আউটপুট হবে −4, কারণ দীর্ঘতম পাটিগণিত ক্রম হল [7,5, 3,1]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি মানচিত্র m সংজ্ঞায়িত করুন
- 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
