Hiệu lớn nhất – Phú Thọ 2025-2026

Đề bài

Cho dãy số nguyên $a_1, a_2, \dots, a_n$ và số nguyên dương $k$ .

Yêu cầu: Thực hiện phép xóa $k$ phần tử sao cho chênh lệch nhỏ nhất giữa 2 phần tử bất kỳ còn lại là lớn nhất.

Dữ liệu vào

Dòng đầu chứa hai số nguyên dương $n, k$ ( $k \le n - 2$ );
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ( $|a_i| \le 10^9$ ).

Kết quả ra

Gồm một dòng chứa một số là giá trị lớn nhất tìm được.

Ràng buộc

Subtask 1 (20% số điểm): $n \le 20, k = 1$ ;
Subtask 2 (30% số điểm): $20 < n \le 100$ ;
Subtask 3 (25% số điểm): $100 < n \le 2000$ ;
Subtask 4 (25% số điểm): $2000 < n \le 10^5$ .

Ví dụ

Ví dụ 1

Dữ liệu vào

5 1
4 1 2 3 9

Kết quả ra

Giải thích

Xóa 1 phần tử bất kỳ, thì dãy còn lại luôn tồn tại 2 số tự nhiên liên tiếp nhau, nên độ chênh lệch lớn nhất là 1.

Ví dụ 2

Dữ liệu vào

5 2
10 -5 3 -2 1

Kết quả ra

Giải thích

Trong các cách xóa 2 phần tử bất kỳ, cách xóa chỉ còn lại 3 phần tử [10, -5, 3] có độ chênh lệch nhỏ nhất là 7. Cách xóa này là cách xóa có độ chênh lệch nhỏ nhất giữa các phần tử là lớn nhất.