পাইথনে শূন্য যোগফল যুক্ত সর্বোচ্চ দৈর্ঘ্যের সাবলিস্ট খুঁজে বের করার প্রোগ্রাম

মান লें যে, আমাদের কাছে একটি লিস্ট আছে যার উপাদানগুলো শুধুমাত্র ১ এবং -১। আমাদের লক্ষ্য হল সেই সাবলিস্টটি খুঁজে বের করা যার উপাদানগুলোর যোগফল শূন্য এবং যা সবচেয়ে বড় দৈর্ঘ্যের।

উদাহরণস্বরূপ, ইনপুট যদি হয় nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1], তবে আউটপুট হবে ৮, কারণ সবচেয়ে বড় সাবলিস্ট হল [-1, 1, 1, -1, 1, -1, 1, -1] যার যোগফল ০।

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

এই সমস্যাটি সমাধানের জন্য নিচের ধাপগুলো অনুসরণ করব:

table নামে একটি খালি ম্যাপ (ডিকশনারি) তৈরি করুন।
cs = 0 (বর্তমান সাবলিস্টের যোগফল) এবং max_diff = 0 (সর্বোচ্চ দৈর্ঘ্য) ইনিশিয়ালাইজ করুন।
লিস্টের প্রতিটি ইন্ডেক্স i (০ থেকে len(nums)-1) পর্যন্ত লুপ চালান:
- cs = cs + nums[i] যোগফল আপডেট করুন।
- যদি cs == 0 হয়, তবে max_diff = max(max_diff, i + 1)।
- যদি cs ইতিমধ্যে table-এ থাকে, তবে max_diff = max(max_diff, i - table[cs])।
- অন্যথায়, table[cs] = i সংরক্ষণ করুন।
max_diff রিটার্ন করুন।

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

class Solution:
    def solve(self, nums):
        table = {}
        cs = 0
        max_diff = 0
        for i in range(len(nums)):
            cs += nums[i]
            if cs == 0:
                max_diff = max(max_diff, i + 1)
            if cs in table:
                max_diff = max(max_diff, i - table[cs])
            else:
                table[cs] = i
        return max_diff

ob = Solution()
nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1]
print(ob.solve(nums))

ইনপুট

[1, 1, -1, 1, 1, -1, 1, -1, 1, -1]