Chương trình tìm tổng lớn nhất của K danh sách con lặp lại trong Python

Mô tả bài toán

Cho danh sách nums và số k. Xét danh sách lớn là nums lặp lại k lần. Tìm tổng lớn nhất của một danh sách con liên tiếp trong danh sách lớn đó.

Ví dụ: nums = [2, 4, 5, -4], k = 1 → đầu ra 11 (sublist [2,4,5]).

Giải thuật (Kadane mở rộng cho mảng lặp)

1. Khởi tạo s = ans = lo = 0.
2. Lặp min(k, 2) lần: duyệt qua nums, cập nhật s, lo = min(lo, s), ans = max(ans, s - lo).
3. Trả về ans + max(0, sum(nums)) * max(0, k-2).

Ví dụ mã Python

class Solution:
    def solve(self, nums, k):
        s = ans = lo = 0
        for _ in range(min(k, 2)):
            for x in nums:
                s += x
                lo = min(lo, s)
                ans = max(ans, s - lo)
        return ans + max(0, sum(nums)) * max(0, (k - 2))

ob = Solution()
nums = [2, 4, 5, -4]
k = 1
print(ob.solve(nums, k))

Đầu vào

[2, 4, 5, -4], 1

Đầu ra

11