Bài toán dãy con tăng dài nhất

BÀI TOÁN

Cho một dãy gồm n số nguyên a1, a2, ..., an. Hãy tìm dãy con tăng dài nhất của dãy đã cho.

Dữ liệu:

- Dòng đầu tiên ghi số n

- Dòng thứ hai ghi n số nguyên.

Kết quả:

- Dòng đầu tiên ghi số k cho biết độ dài của dãy con tăng tìm được

- Dòng thứ hai ghi k số cho biết dãy con tăng tìm được

Ví dụ:

Input

8

3 8 1 5 3 4 9 2

Output

4

1 3 4 9

 

HƯỚNG DẪN

CÁCH 1: Độ phức tạp O(n²)

Gọi f[i] là độ dài dãy con tăng dài nhất kết thúc tại phần tử thứ i, ta có:

• Nếu tại một vị trí j < i bất kỳ mà aj < ai thì hiển nhiên phần tử tử i có thể đưa vào thêm dãy tăng dài nhất kết thúc tại vị trí j, do đó f[i] = f[j] + 1
• Nếu không tồn tại bất kỳ giá trị j < i sao cho aj < ai thì hiển nhiên dãy con tăng dài nhất kết thúc tại i chỉ có 1 phần tử.

Tóm lại, ta có:

• Cơ sở QHĐ f[1] = 1
• Công thức QHĐ f[i] = max(1, f[j] + 1 | 1 ≤ j < i và aj < ai)
• Kết quả: max(f[i] | i = 1..n)

Đoạn code cho ý tưởng trên như sau:
    f[1] = 1;
    for (int i = 2; i <= n; ++i) {
        f[i] = 1;
        for (int j = 1; j < i; ++j) {
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        }
    }
    ans = 1;
    for (int i = 1; i <= n; ++i) ans = max(ans, f[i]);

Để truy vết cho công thức trên, ta sử dụng thêm một mảng trace, trong đó trace[i] = j cho biết dãy con tăng dài nhất kết thúc tại vị trí i được hình thành bằng cách thêm phần tử thứ i vào dãy con tăng dài nhất kết thúc tại vị trí j. Dựa vào mảng trace này ta có thể truy vết lại để tìm dãy con tăng dần có độ dài lớn nhất (việc viết code truy vết xem như là một bài tập dành có các bạn đọc).

CÁCH 2: Độ phức tạp O(nlogn)