Dãy con đơn điệu dài nhất

1. Mô hình 

Cho dãy a1,a2,..an. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy.

Đặc trưng:

i) Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng For duyệt qua các phần tử ai trong dãy, các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn vị.
ii) Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu. Đặc trưng này có thể mất đi trong một số bài toán khác tùy vào yêu cầu cụ thể. Chẳng hạn bài Tam giác bao nhau.

2. Công thức QHĐ 

Hàm mục tiêu : f = độ dài dãy con. Vì độ dài dãy con chỉ phụ thuộc vào 1 yếu tố là dãy ban đầu nên bảng phương án là bảng một chiều. Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a1 đến ai và phần tử cuối cùng là ai. Nhận xét với cách làm này ta đã chia 1 bài toán lớn (dãy con của n số) thành các bài toán con cùng kiểu có kích thước nhỏ hơn (dãy con của dãy i số). Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con. Ta có công thức QHĐ để tính L(i) như sau: 
• L(1) = 1. (Hiển nhiên)
• L(i) = max(1, L(j)+1 với mọi phần tử j: 0 < j < i và aj ≤ ai). 
Tính L(i) : phần tử đang được xét là ai .Ta tìm đến phần tử aj < ai có L(j) lớn nhất. Khi đó nếu bổ sung ai vào sau dãy con ...aj ta sẽ được dãy con tăng dần dài nhất xét từ a1...ai.

3. Cài đặt

Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm QHĐ L(i). Đoạn chương trình tính các giá trị của mảng L như sau:
for i := 1 to n do begin
L[i] := 1;
for j:=1 to i–1 do
if (a[j]<=a[i]) and (L[i]<L[j]+1) then
L[i]:=L[j]+1;
end;
Như vậy chi phí không gian của bài toán là O(n), chi phí thời gian là O(n2).