Python에서 순환 하위 목록의 최대 합을 찾는 프로그램

<시간/>

숫자 nums의 목록이 있다고 가정하고 이제 nums의 시작과 끝이 이웃인 숫자의 순환 목록을 고려하십시오. 순환 목록에서 비어 있지 않은 하위 목록의 최대 합계를 찾아야 합니다.

따라서 입력이 nums =[2, 3, -7, 4, 5]와 같으면 출력은 14가 됩니다. 합이 14인 하위 목록 [4, 5, 2, 3]을 사용할 수 있기 때문입니다.

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

max_sum :=음의 무한대, cur_max :=0
min_sum :=양의 무한대, cur_min :=0
숫자의 각 숫자에 대해 수행
- cur_max :=num 및 cur_max + num의 최대값
- max_sum :=max_sum 및 cur_max의 최대값
- cur_min :=num 및 cur_min + num의 최소값
- min_sum :=min_sum 및 cur_min의 최소값
max_sum <=0이면
- max_sum 반환
max_sum의 최대값을 반환하고 (nums의 모든 요소 합계 - min_sum)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

import math
class Solution:
   def solve(self, nums):
      max_sum = -math.inf
      cur_max = 0
      min_sum = math.inf
      cur_min = 0
      for num in nums:
         cur_max = max(num, cur_max + num)
         max_sum = max(max_sum, cur_max)
         cur_min = min(num, cur_min + num)
         min_sum = min(min_sum, cur_min)
      if max_sum <= 0:
         return max_sum
      return max(max_sum, sum(nums) - min_sum)
ob = Solution()
nums = [2, 3, -7, 4, 5]
print(ob.solve(nums))

입력

[2, 3, -7, 4, 5]