Chương trình tìm độ dài của danh sách con dài nhất có tổng bằng 0 bằng Python

Giả sử chúng ta có một danh sách chỉ có hai giá trị 1 và −1. Chúng ta phải tìm độ dài của danh sách con dài nhất có tổng bằng 0.

Vì vậy, nếu đầu vào là nums =[1, 1, −1, 1, 1, −1, 1, −1, 1, −1], thì đầu ra sẽ là 8, vì danh sách con dài nhất là [−1 , 1, 1, −1, 1, −1, 1, −1] có tổng bằng 0.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• table:=một bản đồ trống mới

• cs:=0, max_diff:=0

• đối với tôi trong phạm vi từ 0 đến kích thước của nums - 1, thực hiện

  • cs:=cs + nums [i]

  • nếu cs giống 0 thì

    • max_diff:=tối đa i + 1 và max_diff

  • nếu cs trong bảng thì

    • max_diff:=tối đa của max_diff và (i - table [cs])

  • nếu không,

    • bảng [cs]:=i

• trả về max_diff

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

[1, 1, −1, 1, 1, −1, 1, −1, 1, −1]

Đầu ra

8