Chương trình tìm tổng lớn nhất của hai danh sách con không chồng chéo trong Python

Mô tả bài toán

Cho danh sách nums và hai giá trị x, y. Tìm tổng lớn nhất của hai danh sách con không chồng chéo có độ dài x và y.

Ví dụ: nums = [3, 2, 10, -2, 7, 6], x = 3, y = 1 → đầu ra 22 (chọn [3,2,10] và [7]).

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

1. Tính mảng prefix sum P với P[0]=0.
2. Định nghĩa hàm solve(len1, len2):
   • Tính mảng Q chứa tổng các đoạn độ dài len1.
   • Tính mảng prefix là max prefix của Q.
   • Duyệt vị trí bắt đầu của đoạn thứ hai (độ dài len2), lấy max của prefix[i-len1] + (P[i+len2]-P[i]).
3. Trả về max của solve(x, y) và solve(y, x).

Ví dụ mã Python

class Solution:
    def solve(self, A, len1, len2):
        P = [0]
        for x in A:
            P.append(P[-1] + x)
        def solve(len1, len2):
            Q = [P[i + len1] - P[i] for i in range(len(P) - len1)]
            prefix = Q[:]
            for i in range(len(prefix) - 1):
                prefix[i + 1] = max(prefix[i + 1], prefix[i])
            ans = float("-inf")
            for i in range(len1, len(P) - len2):
                left = prefix[i - len1]
                right = P[i + len2] - P[i]
                ans = max(ans, left + right)
            return ans
        return max(solve(len1, len2), solve(len2, len1))

ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y))

Đầu vào

[3, 2, 10, -2, 7, 6], 3, 1

Đầu ra

22