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

একটি সংখ্যার তালিকা nums এবং একটি ভ্যালু diff দেওয়া আছে। এমন সবচেয়ে লম্বা আর্থমেটিক সাবসিকোয়েন্স খুঁজে বের করতে হবে যেখানে যেকোনো দুটি কনsekutিভ উপাদানের পার্থক্য diff এর সমান।

উদাহরণ: nums = [-1, 1, 4, 7, 2, 10], diff = 3 হলে আউটপুট 4। কারণ সাবসিকোয়েন্স [1, 4, 7, 10] (প্রতিটি পার্থক্য ৩)।

সমাধানের পদ্ধতি

হ্যাশ ম্যাপ (ডিকশনারি) ব্যবহার করে DP সমাধান। seen[x] = মান x দিয়ে শেষ হওয়া সাবসিকোয়েন্সের দৈর্ঘ্য।

• প্রতিটি x ইন nums এর জন্য:
• যদি x - diff ইতিমধ্যে seen-এ থাকে, তবে seen[x] = seen[x - diff] + 1
• অন্যথায় seen[x] = 1 (নতুন সিকোয়েন্স শুরু)
• সর্বোচ্চ মান mx ট্র্যাক করুন।

পাইথন কোড

from collections import defaultdict

def solve(nums, diff):
    seen = defaultdict(int)
    mx = 0
    for x in nums:
        if x - diff in seen:
            seen[x] = seen[x - diff] + 1
        else:
            seen[x] = 1
        mx = max(mx, seen[x])
    return mx

# টেস্ট
nums = [-1, 1, 4, 7, 2, 10]
diff = 3
print(solve(nums, diff))  # আউটপুট: 4

ব্যাখ্যা

defaultdict(int) মিসিং কির জন্য ০ রিটার্ন করে। অ্যারেটি সর্ট করা নাও থাকলে চলে, কারণ আমরা অর্ডার মেনটেইন করছি ইনপুট অনুযায়ী।

সময় জটিলতা

O(n) - একক পাস। স্পেস O(n)।