পাইথনে দিয়ে দিয়ে সর্বোচ্চ দৈর্ঘ্যের অ্যারিথমেটিক সাবসিকোয়েন্স খুঁজে বের করার প্রোগ্রাম

একটি সংখ্যা লিস্ট nums দেওয়া আছে। এমন একটি সাবসিকোয়েন্স খুঁজে বের করতে হবে যাতে সেটি অ্যারিথমেটিক প্রগ্রেশন (AP) গঠন করে—অর্থাৎ প্রতিটি দুটি সন্নিকট উপাদানের পার্থক্য (ডিফারেন্স) একই থাকে। সাবসিকোয়েন্সের সর্বোচ্চ দৈর্ঘ্য বের করতে হবে।

উদাহরণস্বরূপ, nums = [1, 4, 7, 10, 13, 20, 16] হলে আউটপুট ৬, কারণ [1, 4, 7, 10, 13, 16] একটি AP যার कॉमन ডিফারেন্স ৩।

সমাধানের পদ্ধতি (DP + HashMap)

n = len(arr)। যদি n <= 1, n রিটার্ন করুন।
dp = একটি ডিকশনারি (ডিফল্ট ভ্যালু ১), কী: (index, diff), মান: সাবসিকোয়েন্স দৈর্ঘ্য।
res = 0।
i = 1..n-1 এবং j = 0..i-1 জন্য:
- diff = arr[i] - arr[j]।
- dp[i, diff] = dp[j, diff] + 1।
- res = max(res, dp[i, diff])।
res রিটার্ন করুন।

পাইথন কোড উদাহরণ

from collections import defaultdict

class Solution:
    def solve(self, arr):
        n = len(arr)
        if n <= 1:
            return n
        res = 0
        dp = defaultdict(lambda: 1)
        for i in range(1, n):
            for j in range(i):
                diff = arr[i] - arr[j]
                dp[i, diff] = dp[j, diff] + 1
                res = max(res, dp[i, diff])
        return res

ob = Solution()
nums = [1, 4, 7, 10, 13, 20, 16]
print(ob.solve(nums))

ইনপুট

[1, 4, 7, 10, 13, 20, 16]