Hiểu bài toán

Bài toán yêu cầu tìm độ dài của dãy con tăng dài nhất (Longest Increasing Subsequence - LIS) của một dãy số cho trước. Dãy con được định nghĩa là một dãy mới được tạo ra bằng cách chọn các phần tử từ dãy gốc sao cho thứ tự tương đối của chúng được giữ nguyên. Dãy con tăng要求要求 các phần tử trong dãy con phải tăng dần về giá trị (a[i1] < a[i2] < ... < a[i_k]). Ví dụ, với dãy [1, 2, 5, 4, 6, 2], dãy con tăng dài nhất là [1, 2, 4, 6] hoặc [1, 2, 5, 6] có độ dài 4.

Các cách tiếp cận

Cách Quy hoạch động cơ bản (O(n^2))

#include <stdio.h>

int fun(int n, int nums[]) {
    int dp[n];
    int max_len = 1;

    for (int i = 0; i < n; i++) {
        dp[i] = 1; // Mỗi phần tử ít nhất là 1 dãy tăng
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j] && dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
        }
        if (dp[i] > max_len)
            max_len = dp[i];
    }
    return max_len;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng quy hoạch động. Ta định nghĩa dp[i] là độ dài dãy con tăng dài nhất kết thúc tại vị trí i. Với mỗi phần tử thứ i, ta duyệt qua tất cả các phần tử j trước đó (j < i). Nếu a[i] > a[j] thì ta có thể kéo dài dãy con tăng kết thúc tại j lên i, do đó dp[i] = max(dp[i], dp[j] + 1). Giá trị dp[i] ban đầu là 1 (chính nó). Cuối cùng, độ dài dãy con tăng dài nhất là giá trị lớn nhất trong mảng dp. Cách này đơn giản để hiểu và coding nhưng chậm do phải duyệt qua tất cả các cặp (i, j).

Cách Quy hoạch động từ phải sang trái (O(n^2))

#include <stdio.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    int dp[n]; // dp[i] = độ dài LIS bắt đầu từ i
    int ans = 1;

    // Tính từ phải qua trái
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = 1; // ít nhất có chính nó
        for (int j = i + 1; j < n; j++) {
            if (a[j] > a[i]) {
                dp[i] = max(dp[i], 1 + dp[j]);
            }
        }
        ans = max(ans, dp[i]);
    }

    printf("%d\n", ans);
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Đây là biến thể khác của quy hoạch động, tính toán độ dài dãy con tăng dài nhất BẮT ĐẦU TỪ vị trí i (thay vì kết thúc tại i). Ta duyệt mảng từ phải sang trái. dp[i] được tính bằng 1 + max(dp[j]) với mọi j > i mà a[j] > a[i]. Kết quả cuối cùng là max trên toàn bộ dp. Độ phức tạp tính toán tương đương với cách trên, nhưng cách viết này phù hợp với một số dạng bài toán khác (ví dụ: dãy con giảm).

Cách Tối ưu bằng mảng phụ (O(n log n))

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> tails;
    for (int x : a) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }
    cout << tails.size() << endl;
    return 0;
}

• Time Complexity: O(n log n)
• Space Complexity: O(n)

Đây là thuật toán tối ưu nhất để giải quyết bài toán LIS với giới hạn N <= 1000 (và cả N lớn hơn). Ta sử dụng một mảng phụ (hoặc vector) tails để lưu phần tử cuối cùng của các dãy con tăng có độ dài khác nhau. tails[i] là phần tử cuối cùng nhỏ nhất có thể của một dãy con tăng độ dài i+1. Duyệt từng phần tử x trong mảng a, ta dùng hàm lower_bound (tìm kiếm nhị phân) trong C++ để tìm vị trí trong tails có thể chèn x vào. Nếu x lớn hơn tất cả các phần tử trong tails thì ta mở rộng dãy con dài nhất. Ngược lại, ta cập nhật vị trí tìm được bằng x để đảm bảo tính 'nhỏ nhất có thể' cho phần tử cuối cùng của dãy con tăng độ dài tương ứng. Độ dài của tails chính là độ dài LIS.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán LIS có thể được chia nhỏ thành các bài toán con: tìm LIS kết thúc tại từng vị trí hoặc LIS bắt đầu từ từng vị trí.
• Cách tiếp cận O(n log n) không thực sự tìm dãy con trực tiếp mà tìm độ dài bằng cách duy trì một danh sách các phần tử cuối cùng tối ưu cho các độ dài khác nhau.

Lỗi thường gặp

• Nhầm lẫn giữa dãy con (subsequence) và dãy liên tiếp (subarray). Dãy con không cần các phần tử sát nhau trong mảng gốc.
• Trong thuật toán O(n^2), quên khởi tạo giá trị mặc định cho mảng dp (thường là 1 cho mọi phần tử).
• Trong thuật toán O(n log n), sai lầm khi sử dụng upper_bound thay cho lower_bound nếu chỉ cần tìm dãy con không giảm (non-decreasing) thay vì tăng nghiêm ngặt (strictly increasing).