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 tăng là dãy các phần tử trong mảng (không nhất thiết liên tiếp) mà có thứ tự tăng dần. Ví dụ: với mảng [3, 1, 2, 4], LIS là [1, 2, 4] có độ dài 3.

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

Cách Quy hoạch động O(n^2)

#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];

    // dp[i] là độ dài LIS kết thúc tại chỉ số i
    vector<int> dp(n, 1);
    int ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }

    cout << ans;
    return 0;
}

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

Sử dụng quy hoạch động. Với mỗi phần tử a[i], ta duyệt qua tất cả các phần tử trước đó a[j] (j < i). Nếu a[j] < a[i], ta có thể mở rộng LIS kết thúc tại j để tạo thành LIS kết thúc tại i. Ta cập nhật dp[i] = max(dp[i], dp[j] + 1). Đây là cách tiếp cận cơ bản nhưng chậm với n lớn.

Cách Binary Search O(n log n)

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    vector<int> tail; // Lưu phần tử cuối cùng của LIS có độ dài k

    for (int x : a) {
        // Tìm vị trí để chèn x vào tail
        auto it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) {
            tail.push_back(x); // Mở rộng độ dài LIS
        } else {
            *it = x; // Cập nhật phần tử cuối cùng của LIS có độ dài đó
        }
    }

    cout << tail.size();
    return 0;
}

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

Duyệt từng phần tử x trong mảng. Dùng vector tail để lưu phần tử cuối cùng của dãy con tăng có độ dài k (tại vị trí k-1). Với mỗi x, dùng binary search (lower_bound) để tìm vị trí trong tail. Nếu x lớn hơn tất cả, ta mở rộng LIS. Ngược lại, thay thế phần tử đầu tiên >= x bằng x để đảm bảo các LIS tương lai có thể dài hơn. Độ dài của tail chính là kết quả.

Cách Binary Search (Tối ưu bộ nhớ)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    freopen("treelamp.inp", "r", stdin);
    freopen("treelamp.out", "w", stdout);

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

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

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

Đây là biến thể của phương pháp Binary Search tối ưu. Code sử dụng vector<int> l để lưu trữ phần tử cuối cùng của các dãy con tăng. Logic tương tự: nếu phần tử hiện tại lớn hơn hết, thêm vào cuối, nếu không thay thế phần tử đầu tiên lớn hơn hoặc bằng nó. Đây là giải pháp tối ưu và phổ biến nhất cho bài toán LIS.

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

Bài học kinh nghiệm

• Bài toán LIS có thể giải quyết bằng 2 cách chính: Quy hoạch động O(n^2) cho n nhỏ (dưới 5000), và Dùng Binary Search (hoặc cây phân đoạn) O(n log n) cho n lớn (trên 10^5).
• Giả thuật O(n log n) không thực sự tìm dãy con tăng dài nhất trực tiếp, mà duy trì một danh sách các 'đuôi' dãy con tăng tối ưu để đảm bảo độ dài.
• Phương pháp lower_bound trong C++ là công cụ đắc lực để thực hiện tìm kiếm nhị phân trong giải thuật O(n log n).

Lỗi thường gặp

• Lầm tưởng giải thuật O(n log n) tìm được chính xác dãy con tăng dài nhất (thực tế nó chỉ tìm được độ dài).
• Sử dụng mảng cố định hoặc mảng động không đúng cách dẫn đến lỗi bộ nhớ hoặc tràn số với dữ liệu lớn.
• Quên xử lý các trường hợp đặc biệt như dãy giảm dần (kết quả là 1) hoặc dãy tất cả bằng nhau (thường là 1 hoặc theo yêu cầu đề bài nếu cho phép bằng).