মনে করুন একটি পূর্ণসংখ্যার অ্যারে `arr` এবং একটি পূর্ণসংখ্যা `difference` আছে, আমাদের `arr`-এ সবচেয়ে লম্বা সাবসিকোয়েন্সের দৈর্ঘ্য বের করতে হবে যা একটি এরিথমেটিক সিকোয়েন্স যাতে সাবসিকোয়েন্সে আডজেসেন্ট এলিমেন্টগুলোর ডিফারেন্স দেওয়া `difference`-এর সমান থাকে। যদি ইনপুট `[1,5,7,8,5,3,4,2,1]` হয় এবং `difference` = -2, তবে আউটপুট হবে - ৪, কারণ সবচেয়ে লম্বা এরিথমেটিক সিকোয়েন্স হলো `[7,5,3,1]`।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -
- একটি ম্যাপ `m` সংজ্ঞায়িত করুন
- `n` := অ্যারে `arr`-এর আকার, `ans := 0` সেট করুন
- `i` = 0 থেকে `n-1` পর্যন্ত
- `x := arr[i]`
- `m[x] := 1 + m[x - d]`
- `ans := max(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
