মান লেযিয়ে একটি পূর্ণসংখ্যা অ্যারে A দেওয়া আছে, আমাদের A-র মধ্যে সবচেয়ে লম্বা আরিথমেটিক সাবসিকোয়েন্সের দৈর্ঘ্য রিটার্ন করতে হবে। আপনি জানেন যে A-এর একটি সাবসিকোয়েন্স হল A[i_1], A[i_2], ..., A[i_k] যেখানে 0 ≤ i_1 < i_2 < ... < i_k ≤ A.length-1, এবং একটি সিকোয়েন্স B আরিথমেটিক হয় যখন B[i+1] - B[i] সব সময় একই মান থাকে (0 ≤ i < B.length-1)। ইনপুট [9,4,7,2,10] হলে আউটপুট হবে ৩। কারণ সবচেয়ে লম্বা সাবসিকোয়েন্স হল [4,7,10]।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
একটি dp ম্যাপ তৈরি করুন, n := A.size(), ret := 2 সেট করুন
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
j = 0 থেকে i-1 পর্যন্ত লুপ চালান
diff := A[j] - A[i]
dp[i][diff] := 1 + dp[j][diff]
ret := max(1 + dp[i][diff], ret)
return 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
