पायथन में शून्य योग वाली सबसे लंबी सबलिस्ट की लंबाई खोजने का प्रोग्राम

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

उदाहरण के लिए, यदि इनपुट nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1] है, तो आउटपुट 8 होगा, क्योंकि सबसे लंबी सबलिस्ट [-1, 1, 1, -1, 1, -1, 1, -1] है जिसका योग 0 है।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• table := एक खाली मैप (डिक्शनरी)
• cs := 0 (कम्युलेटिव सम), max_diff := 0
• i को 0 से nums के आकार - 1 तक लूप चलाएं:
  • cs := cs + nums[i]
  • यदि cs 0 के बराबर है, तो max_diff := max(i + 1, max_diff)
  • यदि 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(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