Tìm dãy con tăng dài nhất (Longest Increasing Subsequence

Giới thiệu

Cho một dãy số, tìm độ dài của dãy con tăng dài nhất (Longest Increasing Subsequence - LIS). Dãy con không cần phải liên tiếp, chỉ cần các phần tử theo thứ tự tăng dần.

Ví dụ: Dãy {10, 22, 9, 33, 21, 50, 41, 60, 80} có LIS là {10, 22, 33, 50, 60, 80} với độ dài 6.

Đầu vào và Đầu ra

Đầu vào: Dãy: {10, 22, 9, 33, 21, 50, 41, 60, 80}
Đầu ra: Độ dài LIS = 6, Dãy: 10 22 33 50 60 80

Thuật toán O(n²) - Quy hoạch động

LIS_DP(arr, n)
Đầu vào: Mảng arr, kích thước n.
Đầu ra: Độ dài dãy con tăng dài nhất.

Begin
    tạo mảng dp kích thước n, khởi tạo tất cả = 1
    for i := 1 to n-1, do
        for j := 0 to i-1, do
            if arr[i] > arr[j] và dp[i] < dp[j] + 1, then
                dp[i] := dp[j] + 1
        done
    done
    maxLen := max của dp
    return maxLen
End

Thuật toán O(n log n) - Nhị phân tìm kiếm (Patience Sorting)

LIS_Optimal(arr, n)
Đầu vào: Mảng arr, kích thước n.
Đầu ra: Độ dài LIS.

Begin
    tạo mảng tail rỗng
    for i := 0 to n-1, do
        x := arr[i]
        tìm vị trí pos = lower_bound(tail, x) // vị trí đầu tiên >= x
        if pos = tail.size(), then
            thêm x vào cuối tail
        else
            tail[pos] := x
    done
    return tail.size()
End

Ví dụ (C++)

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

// O(n^2) DP
int lisDP(int arr[], int n) {
    vector dp(n, 1);
    for(int i = 1; i < n; i++)
        for(int j = 0; j < i; j++)
            if(arr[i] > arr[j] && dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
    return *max_element(dp.begin(), dp.end());
}

// O(n log n) - Binary Search
int lisOptimal(int arr[], int n) {
    vector tail;
    for(int i = 0; i < n; i++) {
        auto it = lower_bound(tail.begin(), tail.end(), arr[i]);
        if(it == tail.end())
            tail.push_back(arr[i]);
        else
            *it = arr[i];
    }
    return tail.size();
}

// Truy vết dãy LIS (từ DP)
void printLIS(int arr[], int n) {
    vector dp(n, 1), prev(n, -1);
    int maxLen = 1, maxIdx = 0;
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if(dp[i] > maxLen) {
            maxLen = dp[i];
            maxIdx = i;
        }
    }
    vector lis;
    for(int i = maxIdx; i != -1; i = prev[i])
        lis.push_back(arr[i]);
    reverse(lis.begin(), lis.end());
    cout << "LIS: ";
    for(int x : lis) cout << x << " ";
}

int main() {
    int arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    int n = 9;
    cout << "DP O(n^2): Length = " << lisDP(arr, n) << endl;
    cout << "Optimal O(n log n): Length = " << lisOptimal(arr, n) << endl;
    printLIS(arr, n);
}

Kết quả