Dãy con tăng dần dài nhất

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

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

Đầu vào: {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Đầu ra: Độ dài LIS = 6. Dãy con: 0, 2, 6, 9, 13, 15

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

Mảng length[i] lưu độ dài LIS kết thúc tại chỉ số i.

1. Khởi tạo length[0] = 1, các phần tử khác = 0.
2. Với mỗi i từ 1 đến n-1:
   • Với mỗi j từ 0 đến i-1: nếu arr[j] < arr[i] và length[j] > length[i] thì length[i] = length[j].
   • Tăng length[i] lên 1 (thêm arr[i] vào dãy).
3. Kết quả là max của mảng length.

Lưu ý: Có giải pháp O(n log n) dùng tìm kiếm nhị phân, nhưng bản này trình bày phiên bản O(n²) cơ bản.

Ví dụ C++

#include <iostream>
using namespace std;

int longestSubSeq(int subArr[], int n) {
    int length[n] = {0};
    length[0] = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (subArr[j] < subArr[i] && length[j] > length[i])
                length[i] = length[j];
        }
        length[i]++;
    }

    int lis = 0;
    for (int i = 0; i < n; i++)
        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 << "Length of Longest Increasing Subsequence is: " << longestSubSeq(arr, n);
    return 0;
}

Kết quả

Length of Longest Increasing Subsequence is: 6