Khi thiết kế thuật toán Dynamic Programming cho bài toán chuỗi con tăng dài nhất (Longest Increasing Subsequence - LIS), tại sao việc sử dụng thuật toán thuần túy có độ phức tạp O(N^2) lại không được khuyến khích trong các hệ thống xử lý thời gian thực, và làm thế nào để tối ưu lên O(N log N)?

Question

Accepted Answer

Bản chất vấn đề
Bài toán Longest Increasing Subsequence (LIS) là bài toán kinh điển. Cách tiếp cận Quy hoạch động cơ bản dùng vòng lặp kép so sánh từng phần tử với các phần tử đứng trước nó, dẫn đến độ phức tạp thời gian là O(N^2). Với các hệ thống Enterprise xử lý luồng dữ liệu lớn (như chuỗi log, time-series data), độ trễ này là không thể chấp nhận.
Giải pháp kỹ thuật
Để hạ độ phức tạp xuống O(N log N), chúng ta kết hợp Quy hoạch động với thuật toán Binary Search (Tìm kiếm nhị phân). Thay vì lưu trữ tất cả các chuỗi con, ta duy trì một mảng phụ (thường gọi là tails) lưu phần tử nhỏ nhất kết thúc của các chuỗi con tăng có độ dài tương ứng.
Ví dụ minh họa (Thuật toán O(N log N))
function lengthOfLIS(nums) {
    let tails = [];
    for (let x of nums) {
        let left = 0, right = tails.length;
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (tails[mid] < x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (left === tails.length) {
            tails.push(x);
        } else {
            tails[left] = x;
        }
    }
    return tails.length;
}
Kinh nghiệm thực chiến cho Junior

Không bao giờ dừng lại ở giải pháp O(N^2) nếu kích thước đầu vào (Input size) có khả năng vượt quá hàng chục nghìn phần tử.
Cần nắm vững cách sử dụng Binary Search (như hàm lower_bound trong C++ hoặc tự viết hàm tìm kiếm nhị phân trong JavaScript/Python) để áp dụng linh hoạt vào các bài toán tối ưu hóa chuỗi.

Bản chất vấn đề

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi dynamic programming liên quan cùng chủ đề