Chương trình tìm tổng tối đa của danh sách con tròn trong Python

Giả sử chúng ta có một danh sách các số num, bây giờ hãy xem xét một danh sách vòng tròn các num trong đó đầu và cuối của num là hàng xóm của nhau. Chúng ta phải tìm tổng tối đa của một danh sách con không trống trong danh sách vòng tròn.

Vì vậy, nếu đầu vào giống như nums =[2, 3, -7, 4, 5], thì đầu ra sẽ là 14, vì chúng ta có thể lấy danh sách con [4, 5, 2, 3] tổng là 14.

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

• max_sum:=âm vô cực, cur_max:=0

• min_sum:=dương vô cực, cur_min:=0

• đối với mỗi số trong số, thực hiện

  • cur_max:=tối đa là num và cur_max + num

  • max_sum:=tối đa max_sum và cur_max

  • cur_min:=tối thiểu là num và cur_min + num

  • min_sum:=tối thiểu min_sum và cur_min

• nếu max_sum <=0, thì

  • trả về max_sum

• trả về tối đa max_sum và (tổng của tất cả các phần tử tính bằng nums - min_sum)

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

Ví dụ

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

Đầu vào

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

Đầu ra

14