পাইথনে সাবসিকোয়েন্স যেখানে ভ্যালু ডিফারেন্স = ইনডেক্স ডিফারেন্স, সেটির ম্যাক্সিমাম সম

দেওয়া লিস্ট nums। একটি স্ট্রিক্টলি ইনক্রিজিং সাবসিকোয়েন্স খুঁজতে হবে যাতে প্রতিটি কনসেকিউটিভ জোড়ার জন্য ভ্যালুর ডিফারেন্স তাদের ইনডেক্স ডিফারেন্সের সমান হয়। সাবসিকোয়েন্সের ম্যাক্সিমাম সম বের করতে হবে।

উদাহরণ: nums=[6,7,9,9,8,5] → সাবসিকোয়েন্স [6,7,9] ইনডেক্স [0,1,3] → ভ্যালু ডিফ: ১,২; ইনডেক্স ডিফ: ১,২ → ম্যাচ → সম = ২২।

গাণিতিক ইনসাইট + হ্যাশম্যাপ

শর্ত: nums[j] - nums[i] = j - i → nums[j] - j = nums[i] - i।

অর্থাৎ, nums[i] - i ভ্যালু একই থাকলে সেগুলো একটি বৈধ সাবসিকোয়েন্স বানাতে পারে। প্রতিটি key = nums[i] - i গ্রুপের মানের যোগফল বের করুন, সর্বোচ্চটি আউটপুট।

পাইথন কোড

from collections import defaultdict

class Solution:
    def solve(self, nums):
        d = defaultdict(int)
        for i, x in enumerate(nums):
            d[x - i] += x
        return max(d.values())

ob1 = Solution()
print(ob1.solve([6, 7, 9, 9, 8, 5]))  # 22

টাইম কমপ্লেক্সিটি: O(n), স্পেস: O(n)। খুবই এলিগ্যান্ট O(n) সমাধান।