Chương trình tìm tổng lớn nhất bằng cách loại bỏ K số từ hai đầu trong Python

Mô tả bài toán

Cho danh sách nums và số k. Phải xóa đúng k phần tử, mỗi lần xóa từ đầu hoặc cuối. Tìm tổng lớn nhất của các phần tử bị xóa.

Ví dụ: nums = [2, 4, 5, 3, 1], k = 2 → đầu ra 6 (xóa 2 và 4).

Giải thuật (Cửa sổ trượt)

1. window = sum(nums[:k]), ans = window.
2. Với i từ 1 đến k:
   • window -= nums[k - i] (bỏ phần tử từ đầu).
   • window += nums[-i] (thêm phần tử từ cuối).
   • ans = max(ans, window).
3. Trả về ans.

Ví dụ mã Python

class Solution:
    def solve(self, nums, k):
        window = sum(nums[:k])
        ans = window
        for i in range(1, k + 1):
            window -= nums[k - i]
            window += nums[-i]
            ans = max(ans, window)
        return ans

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

Đầu vào

[2, 4, 5, 3, 1], 2

Đầu ra

6