ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি অ্যারে রয়েছে, আমাদেরকে A-তে দীর্ঘতম পাটিগণিতিক অনুগামীর দৈর্ঘ্য ফেরত দিতে হবে। আপনি জানেন যে A-এর পরবর্তী একটি তালিকা A[i_1], A[i_2], ..., A[ i_k] 0 <=i_1
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি মানচিত্র তৈরি করুন dp, n :=A এর আকার, ret :=2
সেট করুন -
0 থেকে n – 1
রেঞ্জের i জন্য-
j-এর জন্য 0 থেকে i – 1
পরিসরে-
পার্থক্য :=A[j] – A[i]
-
dp[i, diff] :=1 + dp[j, diff]
-
ret :=সর্বোচ্চ 1 + dp[i, diff] এবং ret
-
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: int longestArithSeqLength(vector<int>& A) { unordered_map <int, unordered_map <int, int> > dp; int n = A.size(); int ret = 2; for(int i = 0; i < n; i++){ for(int j = 0; j < i; j++){ int diff = A[j] - A[i]; dp[i][diff] = 1 + dp[j][diff]; ret = max(1 + dp[i][diff], ret); } } return ret; } }; main(){ vector<int> v1 = {9,4,7,2,10}; Solution ob; cout << (ob.longestArithSeqLength(v1)); }
ইনপুট
[9,4,7,2,10]
আউটপুট
3