Chương trình C++ tìm dãy con tăng dần dài nhất

Dãy con tăng dần dài nhất (Longest Increasing Subsequence - LIS) là một dãy con mà mỗi phần tử đều lớn hơn phần tử trước nó.

Ở đây chúng ta sẽ tìm độ dài của dãy con tăng dần dài nhất từ một tập hợp các số nguyên.

Đầu vào: Tập hợp số nguyên {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} 
Đầu ra: Độ dài dãy con tăng dần dài nhất. Ở đây là 6. Dãy con là 0, 2, 6, 9, 13, 15.

Thuật toán

longestSubSeq(subarray, n)

Đầu vào: Mảng con và kích thước của mảng con.

Đầu ra: Độ dài dãy con tăng dần dài nhất.

Bắt đầu
    Khai báo mảng length kích thước n
    Khởi tạo tất cả phần tử của length = 0
    Với i := 1 đến n-1, thực hiện
        Với j := 0 đến i-1, thực hiện
            Nếu subarray[j] < subarray[i] và length[j] > length[i], thì
                length[i] := length[j]
        Kết thúc vòng lặp j
        Tăng length[i] lên 1
    Kết thúc vòng lặp i
    lis := 0
    Với i := 0 đến n-1, thực hiện
        lis := max(lis, length[i])
    Kết thúc vòng lặp
    Trả về lis
Kết thúc

Mã ví dụ

#include <iostream> 
using namespace std; 

int longestSubSeq(int subArr[], int n) { 
    int length[n] = { 0 }; //khởi tạo tất cả length = 0 
    length[0] = 1; 
    //dãy con kết thúc bằng subArr[0] có độ dài 1 
    for (int i = 1; i < n; i++) { 
        //bỏ qua phần tử đầu, từ phần tử thứ 2 trở đi 
        for (int j = 0; j < i; j++) { 
            //dãy con kết thúc bằng subArr[j] 
            if (subArr[j] < subArr[i] && length[j] > length[i]) 
                length[i] = length[j]; 
        } 
        length[i]++; //thêm arr[i] 
    } 
    int lis = 0; 
    for (int i = 0; i < n; i++) //tìm dãy con tăng dần dài nhất 
        lis = max(lis, length[i]); 
    return lis; 
} 

int main() { 
    int arr[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; 
    int n = 16; 
    cout << "Độ dài dãy con tăng dần dài nhất: " << longestSubSeq(arr, n); 
    return 0; 
}

Kết quả

Độ dài dãy con tăng dần dài nhất: 6