파이썬에서 합이 0인 가장 긴 하위 목록의 길이를 찾는 프로그램

1과 −1 값이 두 개만 있는 목록이 있다고 가정합니다. 합이 0인 가장 긴 하위 목록의 길이를 찾아야 합니다.

따라서 입력이 nums =[1, 1, −1, 1, 1, −1, 1, −1, 1, −1]과 같으면 가장 긴 하위 목록이 [−1이므로 출력은 8이 됩니다. , 1, 1, −1, 1, −1, 1, −1] 합이 0입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

table :=새로운 빈 지도
cs :=0, max_diff :=0
범위 0에서 nums - 1의 크기에 있는 i에 대해 다음을 수행합니다.
- cs :=cs + 숫자[i]
- cs가 0과 같으면
  - max_diff :=i + 1 및 max_diff의 최대값
- cs가 테이블에 있으면
  - max_diff :=max_diff의 최대값 및 (i − table[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]