Chương trình kiểm tra tách danh sách thành các dãy con tăng chặt độ dài ≥ k trong Python

Cho danh sách số nums và số nguyên k. Kiểm tra có thể chia thành các dãy con (không cần liên tiếp) sao cho mỗi dãy có độ dài ≥ k và tăng chặt (strictly increasing).

Ví dụ: nums = [6, 7, 5, 10, 13], k = 2 → tách thành [5, 6] và [7, 10, 13] → True.

Giải thuật (Dựa trên tần suất tối đa)

Số lượng dãy con tối thiểu cần thiết bằng tần suất lớn nhất của bất kỳ số nào (vì các số trùng lặp phải nằm ở dãy khác nhau). Nếu max_freq * k <= n thì có thể chia.

• Đếm tần suất, tìm max_count.
• Trả về max_count * k <= len(nums).

Mã nguồn Python

from collections import Counter

class Solution:
    def solve(self, nums, k):
        c = Counter(nums)
        max_count = max(c.values())
        return max_count * k <= len(nums)

ob = Solution()
nums = [6, 7, 5, 10, 13]
k = 2
print(ob.solve(nums, k))  # Output: True

Đầu vào

[6, 7, 5, 10, 13], 2

Đầu ra

True