Chương trình tìm tổng lớn nhất dãy con tròn trong Python

Cho danh sách nums, coi như danh sách tròn (đầu và cuối liền nhau). Tìm tổng lớn nhất của dãy con không rỗng trong danh sách tròn.

Ví dụ: nums = [2, 3, -7, 4, 5] → kết quả 14 (dãy [4, 5, 2, 3]).

Giải thuật (Kadane biến thể - O(n))

Tổng max dãy con tròn = max(tổng max dãy con thường, tổng tất cả - tổng min dãy con).

1. Khởi tạo , , , .
2. Duyệt trong :
   • ; .
   • ; .
3. Nếu (tất cả số âm): trả về .
4. Ngược lại: trả về .

Ví dụ minh họa

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))  # Output: 14

Đầu vào

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

Đầu ra

14