1) Phát biểu

Cho dãy A gồm n số nguyên, ký hiệu[a0a1,…, an-1] . Tìm một dãy con đơn điệu tăng dài nhất của dãy A, biết một dãy con của A là dãy có được từ A bằng cách xóa đi một số phân tử của A. Ví dụ: dãy[1, 5, 9, 2, 3, 11, 8, 10, 4] có dãy con đơn điệu tăng dài nhất là [1, 2, 3, 8, 10].

2) Nhận định ban đầu

Số dãy con của a

Chúng ta có thể xem mỗi dãy con a của A tương ứng với một chuỗi nhị phân b độ dài n, trong đó,  bi = 0 nghĩa là ai không thuộc a và ngược lại bi = 1 nghĩa là ai thuộc a. Ví dụ nếu A = [1, 3, 2, 3] thì dãy con tương ứng với chỗi nhị phân b = 1010 là [1, 3]. Như vậy, số dãy con của A cũng chính là số chuỗi nhị phân có độ dài n chính là 2n. Mặc dù có thể với 2 chuỗi nhị phân khác nhau sẽ tương ứng với cùng một dãy con (với mảng A = [1, 3, 2, 3], hai chuỗi 1100 và 1001 cùng tương ứng với dãy con [1, 3]), nhưng nếu lập trình bình thường để duyệt tất cả các dãy con của A thì phải duyệt 2n phần tử. Với n = 100 thì có đến 2100≈ 1030 dãy con.

Phương án khả thi

Phương án duyệt tất cả các dãy con để tìm kết quả tối ưu có độ phức tạp là O(2n), rõ ràng là không khả thi khi n lớn. Có cách nào khác để tìm được dãy con tối ưu mà không phải duyệt tất cả? Chúng ta thử cân nhắc phương pháp Quy hoạch động hay Đệ quy xem thử thế nào, nghĩa là tìm cách chia bài toán ban đầu thành các bài toán con :-?

3) Ý tưởng

  • Tìm cách chia nhỏ bài toán
  • Tìm cách “ghép” các bài toán nhỏ để giải bài toán lớn hơn
  • Công thức truy hồi

4) Đánh giá

– Độ phức tạp của thuật toán là O(n2).

5) Code

#include <stdio.h>
#include <conio.h>
#define m 8
 
void main()
{
    int a[m] = {1,4,5,9,2,6,7,10}; //dãy A
    int l[m]; //l[i]: độ dài DCĐĐTDN của dãy a[0],..,a[i] mà có chứa a[i]
    int t[m]; //t[i]: vị trí phần tử ngay phía trước a[i] trong DCĐĐTDN của dãy a[0],..,a[i]
 
    // Bước 1. Lập bảng phương án (tính mảng L và T)
    l[0] = 1; t[0] = -1;
    for (int i=1; i<m; i++)
    {
        int max = 1; //độ dài DCĐĐTDN của dãy a[0],..,a[i]
        for (int j=0; j<i; j++)
            if (a[j] < a[i] && max < l[j] + 1)
            {
                max = l[j] + 1;
                t[i] = j; //để sau này truy vết: phần tử ngay phía sau a[i] là a[j]
            }
        l[i] = max;
    }
 
    //Bước 2. Tìm vị trí cuối của DCĐĐTDN
    int lMax = 0; //độ dài DCĐĐTDN của dãy A
    int viTriMax = 0; //a[viTriMax] sẽ là phần tử cuối cùng trong DCĐĐTDN của dãy A
    for (int i=1; i<m; i++)
        if (l[i] > lMax)
        {
            lMax = l[i];
            viTriMax = i;
        }
 
    //Bước 3. Truy vết để tìm DCĐĐTDN (kq): dựa vào T và viTriMax
    int kq[m];
    int k = lMax-1;
    do {
        kq[k] = a[viTriMax];
        k--;
        viTriMax = t[viTriMax];
    }while (k>=0);
 
    //Bước 4. Xuất kết quả
    printf("\n- Day A: "); //Hiển thị dãy A
    for (int i=0; i<m; i++) printf("%d ", a[i]);
    printf("\n- Day con don dieu tang dai nhat: "); //Hiển thị DCĐĐTDN
    for (int i=0; i<lMax; i++) printf("%d ", kq[i]);
    printf("\n  (gom %d phan tu)", lMax);
    getch(); //dừng màn hình để xem kết quả
}