ধরুন আমাদের একটি তালিকা আছে মাত্র দুটি মান 1 এবং −1। আমাদের দীর্ঘতম সাবলিস্টের দৈর্ঘ্য খুঁজে বের করতে হবে যার যোগফল 0।
সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[1, 1, −1, 1, 1, −1, 1, −1, 1, −1], তাহলে আউটপুট হবে 8, কারণ দীর্ঘতম সাবলিস্ট হল [−1] , 1, 1, −1, 1, −1, 1, −1] যার যোগফল 0৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
টেবিল :=একটি নতুন খালি মানচিত্র
-
cs :=0, max_diff :=0
-
আমি 0 থেকে সংখ্যার আকার − 1 এর মধ্যে, কর
-
cs :=cs + nums[i]
-
যদি cs 0 এর মত হয়, তাহলে
-
max_diff :=সর্বাধিক i + 1 এবং max_diff
-
-
যদি cs টেবিলে থাকে, তাহলে
-
max_diff :=max_diff এর সর্বোচ্চ এবং (i − টেবিল[cs])
-
-
অন্যথায়,
-
টেবিল[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(i + 1, max_diff)
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]
আউটপুট
8
