C++ এ দীর্ঘতম পাটিগণিত ক্রম

ধরুন আমাদের কাছে পূর্ণসংখ্যার একটি অ্যারে রয়েছে, আমাদেরকে 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