Dãy con tăng dài nhất trong O(N log N)

Mục tiêu kiến thức

• Hiểu hạn chế của giải thuật Quy hoạch động LIS kinh điển O(N²) khi dữ liệu lớn.
• Nắm vững thuật toán Xếp bài kiên nhẫn (Patience Sorting) kết hợp Tìm kiếm nhị phân bisect_left.
• Đạt độ phức tạp thời gian O(N log N) để vượt qua giới hạn N = 10⁵ phần tử trong 1.0 giây.

Mô tả bài toán

Hệ thống đánh giá hiệu năng huấn luyện mô hình tại AI Empire Academy ghi lại chỉ số Accuracy qua các epoch thành một mảng số thực/số nguyên nums. Cần tìm độ dài lớn nhất của một chuỗi các epoch có hiệu năng tăng trưởng nghiêm ngặt liên tục (dãy con không nhất thiết phải liền kề).

Hãy viết hàm length_of_lis(nums: list[int]) -> int trả về độ dài của dãy con tăng nghiêm ngặt dài nhất (Longest Increasing Subsequence - LIS).

Quy tắc thuật toán Patience Sorting:

• Duy trì mảng tails với tails[i] là phần tử nhỏ nhất kết thúc một dãy con tăng độ dài i + 1.
• Mảng tails luôn được duy trì tăng dần nghiêm ngặt.
• Với mỗi phần tử x trong nums:
• Dùng tìm kiếm nhị phân (bisect_left) tìm vị trí idx đầu tiên trong tails sao cho tails[idx] >= x.
• Nếu tìm thấy, ghi đè tails[idx] = x.
• Nếu không tìm thấy (tức x > mọi phần tử trong tails), mở rộng mảng tails.append(x).
• Độ dài LIS chính là len(tails).

Ràng buộc

• 0 ≤ len(nums) ≤ 10⁵.
• -10⁹ ≤ nums[i] ≤ 10⁹.
• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.