Chương trình tìm chênh lệch lớn nhất giữa các giá trị liền kề sau khi xóa k phần tử bằng Python

Cho danh sách nums đã sắp xếp tăng dần. Xóa đi k phần tử sao cho chênh lệch lớn nhất giữa hai phần tử liền kề còn lại là nhỏ nhất có thể. Trả về chênh lệch đó.

Ví dụ: nums = [15, 20, 30, 400, 1500], k = 2 → xóa [400, 1500], chênh lệch lớn nhất còn lại là 10 (giữa 20 và 30).

Giải thuật

• Tính mảng abs_diff chứa chênh lệch giữa các phần tử liên tiếp.
• Sử dụng quy hoạch động đệ quy dp(i, j, cnt): trả về chênh lệch lớn nhất tối thiểu trên đoạn [i, j] sau khi xóa cnt phần tử.
  • Nếu cnt == 0: trả về max của abs_diff[i..j].
  • Ngược lại: trả về min của dp(i+1, j, cnt-1) và dp(i, j-1, cnt-1).
• Gọi dp(0, len(abs_diff)-1, k).

Ví dụ minh họa

class Solution:
    def solve(self, nums, k):
        abs_diff = [nums[i] - nums[i-1] for i in range(1, len(nums))]
        def dp(i, j, cnt):
            if cnt == 0:
                m = 0
                for k in range(i, j+1):
                    m = max(m, abs_diff[k])
                return m
            return min(dp(i+1, j, cnt-1), dp(i, j-1, cnt-1))
        return dp(0, len(abs_diff)-1, k)

ob = Solution()
nums = [15, 20, 30, 400, 1500]
k = 2
print(ob.solve(nums, k))

Đầu vào

[15, 20, 30, 400, 1500], 2

Đầu ra

10