Chương trình tìm tần suất lớn nhất của phần tử sau k phép tăng trong Python

Cho mảng nums và số k. Mỗi phép toán: chọn index, tăng phần tử đó lên 1. Tìm tần suất lớn nhất có thể của một phần tử sau tối đa k phép toán.

Ví dụ: nums = [8,3,6], k = 9 → output = 3 (tăng 3→8 (+5), 6→8 (+2), tổng 7 phép, tần suất 3).

Giải thuật (Sliding window trên mảng đã sort)

• Sort nums tăng dần.
• Cửa sổ [left, right]: cost để đưa tất cả về nums[right] = (nums[right]-nums[right-1])*(right-left) cộng dồn.
• Nếu cost > k: thu hẹp left, khôi phục cost += nums[right] - nums[left], left++.
• Kết quả = right - left + 1 (khi right duyệt hết).

Code Python

def solve(nums, k):
    nums.sort()
    left = 0
    right = 1
    while right < len(nums):
        k -= (nums[right] - nums[right - 1]) * (right - left)
        if k < 0:
            k += nums[right] - nums[left]
            left += 1
        right += 1
    return right - left

nums = [8, 3, 6]
k = 9
print(solve(nums, k))  # 3

Đầu vào / Đầu ra

Input: [8,3,6], 9
Output: 3