Chương trình tìm tổng lớn nhất của 3 dãy con không giao nhau cùng kích thước trong Python

Cho danh sách số nums và số nguyên k. Tìm tổng lớn nhất của 3 dãy con không giao nhau (non-overlapping), mỗi dãy có độ dài k.

Ví dụ: nums = [2,2,2,-6,4,4,4,-8,3,3,3], k=3 → chọn 3 dãy [2,2,2], [4,4,4], [3,3,3] → tổng = 27.

Giải thuật (Prefix Sum + Sliding Window Max)

• Tính mảng tiền tố P (P[0]=0, P[i+1]=P[i]+nums[i]).
• Mảng Q[i] = P[i+k] - P[i] là tổng dãy con độ dài k bắt đầu tại i.
• Xây dựng prefix_max và suffix_max của Q để truy vấn max nhanh.
• Duyệt vị trí dãy giữa i từ k đến len(Q)-k-1, tổng = Q[i] + prefix_max[i-k] + suffix_max[i+k].
• Lấy max của tổng đó.

Mã nguồn Python

class Solution:
    def solve(self, A, K):
        P = [0]
        for x in A:
            P.append(P[-1] + x)
        Q = [P[i + K] - P[i] for i in range(len(P) - K)]
        prefix = Q[:]
        suffix = Q[:]
        for i in range(len(Q) - 1):
            prefix[i + 1] = max(prefix[i + 1], prefix[i])
            suffix[~(i + 1)] = max(suffix[~(i + 1)], suffix[~i])
        return max(Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K))

ob = Solution()
nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3]
k = 3
print(ob.solve(nums, k))  # Output: 27

Đầu vào

[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], 3

Đầu ra

27