Longest Increasing Subsequence

Bài toán

Cho mảng số nguyên nums. Tìm độ dài của dãy con tăng dài nhất (Longest Increasing Subsequence - LIS). Dãy con không cần liên tiếp.

Ví dụ:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Dãy con: [2, 3, 7, 101] hoặc [2, 3, 7, 18], [2, 5, 7, 101]...

Phân Tích & Tiếp Cận

Cách 1: DP ($O(n^2)$)

dp[i] = Độ dài LIS kết thúc tại index i. Để tính dp[i], ta so sánh nums[i] với tất cả các phần tử trước đó nums[j] ($j < i$). Nếu nums[i] > nums[j], ta có thể nối nums[i] vào sau dãy kết thúc tại j. dp[i] = max(dp[j]) + 1.

function lengthOfLIS(nums: number[]): number {
    const dp = new Array(nums.length).fill(1); // Mặc định mỗi số là 1 dãy độ dài 1

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Math.max(...dp);
}

Cách 2: Patience Sorting & Binary Search ($O(n \log n)$) - Nâng cao

Ta duy trì một mảng phụ tails (hoặc sub). tails[i] lưu giá trị nhỏ nhất có thể của phần tử cuối cùng của một dãy con tăng độ dài i+1. Mục tiêu: Giữ các số trong tails càng nhỏ càng tốt để có cơ hội nối dài dãy.

Duyệt qua từng số num trong nums:

• Nếu num lớn hơn tất cả phần tử trong tails -> Push vào cuối (tăng độ dài dãy).
• Nếu không -> Tìm vị trí đầu tiên trong tails mà >= num và thay thế nó. (Thay số lớn bằng số nhỏ giúp tiềm năng mở rộng tốt hơn). Việc tìm vị trí dùng Binary Search.

function lengthOfLIS(nums: number[]): number {
    const tails: number[] = [];

    for (const num of nums) {
        let left = 0, right = tails.length - 1;
        
        // Binary Search vị trí
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        if (left === tails.length) {
            tails.push(num);
        } else {
            tails[left] = num;
        }
    }

    return tails.length;
}

Pattern Nhận Diện

• Dãy con không liên tiếp (Subsequence) + Thứ tự (Increasing).
• Nếu N nhỏ (1000) -> $O(n^2)$ ok. Nếu N lớn ($10^5$) -> Phải dùng $O(n \log n)$.