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ố nguyên cho trước. Dãy con được hiểu là các phần tử không nhất thiết liên tiếp nhưng phải giữ nguyên thứ tự xuất hiện trong dãy ban đầu. Dãy con tăng yêu cầu các phần tử phải tăng dần về giá trị (strictly increasing).

Ví dụ: Với dãy [2, 7, 4, 3, 8], ta có các dãy con tăng như [2, 7, 8], [2, 4, 8], [4, 8],... trong đó dãy con tăng dài nhất có độ dài là 3.

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

Cách Dynamic Programming 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];
    }

    vector<int> dp(n, 1);
    int ans = 1;

    for (int i = 1; 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 tính dp[i] là độ dài dãy con tăng dài nhất kết thúc tại a[i]. Để tính dp[i], ta duyệt qua tất cả các phần tử trước đó a[j] (j < i) và nếu a[j] < a[i] thì dp[i] = max(dp[i], dp[j] + 1). Đáp án là giá trị lớn nhất trong mảng dp. Phương pháp này đơn giản nhưng không đủ nhanh cho n lớn.

Cách Greedy với Binary Search (Patience Sorting)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> tails;
    tails.reserve(n);

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;

        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x);
        } else {
            *it = x;
        }
    }

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

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

Ta duy trì một mảng 'tails' trong đó tails[i] là phần tử kết thúc nhỏ nhất có thể của một dãy con tăng có độ dài i+1. Với mỗi phần tử x mới, ta dùng binary search (lower_bound) để tìm vị trí thích hợp trong 'tails'. Nếu x lớn hơn tất cả phần tử trong 'tails' thì ta thêm x vào cuối (tăng độ dài LIS). Ngược lại, ta thay thế phần tử đầu tiên >= x bằng x để giữ cho các dãy con có độ dài bằng nhau có phần tử kết thúc nhỏ nhất. Độ dài của 'tails' chính là đáp án.

Cách Multiset Approach

#include <iostream>
#include <set>
using namespace std;

int main() {
    int n;
    cin >> n;
    multiset<int> mulse;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        mulse.insert(a);
        auto it = mulse.lower_bound(a);
        it++; // Chuyển sang phần tử tiếp theo
        if (it != mulse.end()) {
            mulse.erase(it);
        }
    }

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

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

Sử dụng một multiset để lưu các phần tử kết thúc của các dãy con tăng. Khi đọc một số a, ta thêm nó vào multiset. Sau đó, ta tìm phần tử ngay sau a trong multiset (dùng lower_bound). Nếu tồn tại phần tử này, ta xóa nó đi. Ý tưởng là a sẽ 'thay thế' phần tử lớn hơn nó trong cùng một dãy con, giúp tạo điều kiện cho các phần tử tiếp theo có thể nối dài dãy con đó dễ dàng hơn. Cuối cùng, kích thước của multiset chính là độ dài LIS.

Cách Dynamic Programming với Fenwick Tree/Segment Tree

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int get_max(const vector<int>& bit, int idx) {
    int res = 0;
    while (idx > 0) {
        res = max(res, bit[idx]);
        idx -= idx & -idx;
    }
    return res;
}

void update(vector<int>& bit, int idx, int val) {
    while (idx < bit.size()) {
        bit[idx] = max(bit[idx], val);
        idx += idx & -idx;
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> temp;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        temp.push_back(a[i]);
    }

    // Coordinate Compression
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());

    int max_val = temp.size();
    vector<int> bit(max_val + 1, 0);
    int ans = 0;

    for (int i = 0; i < n; i++) {
        int x = lower_bound(temp.begin(), temp.end(), a[i]) - temp.begin() + 1;
        int current_len = get_max(bit, x - 1) + 1;
        update(bit, x, current_len);
        ans = max(ans, current_len);
    }

    cout << ans;
    return 0;
}

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

Phương pháp này cũng dựa trên quy hoạch động: dp[x] là độ dài LIS kết thúc bằng giá trị x. Thay vì duyệt mảng, ta dùng Fenwick Tree (BIT) để tối ưu hóa việc lấy max trên đoạn [1, x-1]. Vì giá trị a[i] có thể lớn nhưng số lượng phần tử chỉ là n, ta cần nén tọa độ (Coordinate Compression) để ánh xạ các giá trị về dải [1, n]. BIT cho phép query max và update trong O(log n).

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

Bài học kinh nghiệm

• Bài toán LIS có nhiều cách tiếp cận với độ phức tạp khác nhau. Với n <= 10^6, O(n^2) là không khả thi, cần dùng O(n log n).
• Cách tiếp cận 'tails array' (Patience Sorting) là hiệu quả và phổ biến nhất trong thi đấu, chỉ cần mảng động và binary search.
• Một biến thể quan trọng là bài toán 'Dãy con tăng dài nhất không nhất thiết liên tiếp' (thuật toán O(n log n) kinh điển).

Lỗi thường gặp

• Sử dụng lower_bound thay cho upper_bound: Nếu dùng upper_bound, ta sẽ cho phép các phần tử bằng nhau trong dãy con tăng (strictly increasing), nhưng thực tế lower_bound là chính xác nếu ta cập nhật phần tử tại vị trí tìm thấy. Tuy nhiên, logic cập nhật *it = x của các solution trên dùng lower_bound là chuẩn cho bài toán strictly increasing.
• Lỗi tràn số nguyên: Với các giải pháp O(n^2) hoặc O(n log n) cơ bản, cần lưu ý kiểu dữ liệu của mảng đầu vào. Solution 1 dùng long long để an toàn.
• Quên tối ưu hóa I/O: Với n lớn (~10^6), việc dùng cin/cout mặc định rất chậm. Cần dùng ios::sync_with_stdio(false); cin.tie(nullptr); như trong các solution.