Editorial for dctdn3: Dãy con tăng dài nhất (Bản khó)

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ần tìm phải thỏa mãn: các phần tử giữ nguyên thứ tự xuất hiện trong dãy ban đầu và có giá trị tăng dần. Với N lên đến 100,000, giải pháp duyệt qua tất cả các dãy con (O(2^N)) không khả thi.

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

    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 mảng dp[i] để lưu độ dài dãy con tăng dài nhất kết thúc tại phần tử thứ i. Với mỗi i, ta duyệt qua tất cả j < i, nếu a[j] < a[i] thì cập nhật dp[i] = max(dp[i], dp[j] + 1). Độ phức tạp O(n^2) không xử lý được n=100,000 trong thời gian cho phép.

Cách Tối ưu với mảng phụ và Binary Search

#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> tail;
    for (int x : a) {
        auto it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) {
            tail.push_back(x);
        } else {
            *it = x;
        }
    }

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

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

Dùng mảng tail để lưu phần tử cuối cùng của các dãy con tăng có độ dài khác nhau. tail[i] là phần tử cuối cùng nhỏ nhất của dãy con tăng có độ dài i+1. Với mỗi phần tử a[i], dùng binary search (lower_bound) để tìm vị trí phù hợp trong tail và cập nhật. Nếu a[i] lớn hơn tất cả phần tử trong tail thì mở rộng độ dài dãy.

Cách Phân tích từ các giải pháp C

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define MAX 100005
long long tail[MAX];
long long a[MAX];

int bisrch(long long tail[], int len, long long x) {
    int left = 1, right = len;
    int result = len + 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (tail[mid] >= x) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    int len = 0;
    for (int i = 0; i < n; i++) {
        int pos = bisrch(tail, len, a[i]);
        tail[pos] = a[i];
        if (pos > len) {
            len = pos;
        }
    }
    printf("%d", len);
    return 0;
}

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

Đây là bản cài đặt trực tiếp của thuật toán patience sorting. Mảng tail lưu các phần tử cuối cùng của các pile (tương ứng dãy con tăng). Dùng binary search để tìm vị trí đặt phần tử mới: tìm pile có phần tử cuối cùng >= a[i] đầu tiên, thay thế nó. Nếu không tìm thấy, tạo pile mới ở cuối. Độ dài LIS chính là số lượng pile.

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

Bài học kinh nghiệm

• Bài toán có thể quy hoạch động với độ phức tạp O(n^2) nhưng cần tối ưu cho n lớn.
• Giải pháp O(n log n) sử dụng mảng phụ tail, trong đó tail[i] là phần tử cuối cùng nhỏ nhất của dãy con tăng độ dài i+1.
• Binary search (lower_bound) giúp tìm vị trí cập nhật trong mảng tail một cách nhanh chóng.

Lỗi thường gặp

• Lầm tưởng giữa dãy con (subsequence) và dãy liên tiếp (subarray) - các phần tử không nhất thiết phải liền kề.
• Sử dụng O(n^2)导致 TLE (Time Limit Exceeded) với n = 100,000.
• Lỗi index khi cài đặt binary search thủ công, đặc biệt với các biến left, right, result.