सबसे लंबे सबलिस्ट की लंबाई खोजने का कार्यक्रम जिसका योग पायथन में 0 है

मान लीजिए कि हमारे पास केवल दो मानों 1 और -1 के साथ एक सूची है। हमें सबसे लंबे सबलिस्ट की लंबाई ज्ञात करनी है जिसका योग 0 है।

इसलिए, यदि इनपुट nums =[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 तक के लिए, करें

  • सीएस:=सीएस + अंक[i]

  • अगर सीएस 0 के समान है, तो

    • max_diff :=अधिकतम i + 1 और max_diff

  • यदि cs तालिका में है, तो

    • max_diff :=अधिकतम max_diff और (i - तालिका[cs])

  • अन्यथा,

    • टेबल [सीएस] :=मैं

• वापसी 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