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

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 nghiêm ngặt (strictly increasing subsequence) dài nhất của một dãy số cho trước. Dãy con yêu cầu các phần tử phải lấy theo thứ tự xuất hiện trong dãy ban đầu nhưng không nhất thiết phải liên tiếp nhau, và các giá trị phải tăng dần. Ví dụ: với dãy [1, 2, 5, 4, 6, 2], các dãy con tăng hợp lệ có thể là [1, 2, 5], [1, 2, 4, 6], [1, 2, 6],... trong đó dãy dài nhất 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 <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 vị trí i. 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] thì ta có thể nối a[i] vào sau dãy con kết thúc tại j, do đó dp[i] = max(dp[i], dp[j] + 1). Cuối cùng, đáp án là giá trị lớn nhất trong mảng dp. Phương pháp này đơn giản nhưng chậm với n lớn.

Cách Tối ưu bằng tìm kiếm nhị phân (O(n log n))

#include <stdio.h>
#include <string.h>

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

int bisrch(int tail[], int len, int 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("%d", &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)

Sử dụng mảng tail[] để lưu phần tử cuối cùng của dãy con tăng có độ dài k. Với mỗi phần tử a[i], ta dùng tìm kiếm nhị phân để tìm vị trí thích hợp trong tail[]: nếu a[i] lớn hơn tất cả phần tử trong tail[] thì mở rộng dãy, ngược lại thay thế phần tử đầu tiên trong tail[] lớn hơn hoặc bằng a[i] bằng a[i]. Điều này giúp duy trì cơ hội tạo ra dãy dài hơn trong tương lai. Mảng tail[] luôn tăng dần nên có thể dùng binary search.

Cách Tối ưu bằng tìm kiếm nhị phân (Phát hiện lỗi Logic)

// Lưu ý: Solution 2 trong bài có lỗi logic
// Tìm số lớn nhất nhỏ hơn x, sau đó chèn vào sau
// Logic đúng phải là tìm vị trí chèn sao cho tail[] tăng dần
// Dưới đây là phiên bản sửa lỗi:
#include <stdio.h>
#include <stdlib.h>

int search(int tail[], int len, int x) {
    int l = 1, r = len;
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (tail[mid] < x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

int main() {
    int n;
    scanf("%d", &n);
    int *a = (int*)malloc(n * sizeof(int));
    int *tail = (int*)malloc((n + 1) * sizeof(int));

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

    int len = 0;
    for (int i = 0; i < n; i++) {
        int j = search(tail, len, a[i]);
        tail[j + 1] = a[i];
        if (j + 1 > len) len = j + 1;
    }

    printf("%d", len);
    free(a);
    free(tail);
    return 0;
}

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

Đây là cách tiếp cận thay thế, tìm vị trí chèn dựa trên phần tử nhỏ hơn a[i] nhất. Tuy nhiên, cách này thường khó hiểu hơn và dễ sai nếu không xử lý đúng điều kiện biên. Solution 2 trong bài nộp ban đầu có thể chưa tối ưu hoàn toàn logic tăng dần. Dù sao về bản chất vẫn là tìm kiếm nhị phân O(log n) cho mỗi phần tử.

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 O(n log n) nhờ duy trì mảng tail[] chứa phần tử cuối cùng của dãy con có độ dài k.
• Tìm kiếm nhị phân giúp thay thế O(n) duyệt mảng bằng O(log n).
• Mảng tail[] luôn được duy trì tăng dần, cho phép áp dụng binary search.

Lỗi thường gặp

• Lầm tưởng rằng dãy con tăng phải liên tiếp (thực tế chỉ cần giữ nguyên thứ tự).
• Sai lệch trong logic binary search: cần tìm phần tử >= x (hoặc < x tùy cách cài đặt) để thay thế đúng.
• Quên trường hợp a[i] lớn hơn tất cả phần tử trong tail[] (cần mở rộng độ dài dãy).