Giải thuật và lập trình: §3.1. Dãy con đơn điệu tăng dài nhất

Cho dãy số nguyên A = a₁, a₂, …, a_n. (n £ 5000, -10000 £ a_i £ 10000). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Như vậy A có 2ⁿ dãy con.

Yêu cầu: Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất.

Ví dụ: A = (1, 2, 3, 4, 9, 10, 5, 6, 7). Dãy con đơn điệu tăng dài nhất là: (1, 2, 3, 4, 5, 6, 7).

Input: file văn bản INCSEQ.INP

• Dòng 1: Chứa số n
• Dòng 2: Chứa n số a₁, a₂, …, a_n cách nhau ít nhất một dấu cách

Output: file văn bản INCSEQ.OUT

• Dòng 1: Ghi độ dài dãy con tìm được
• Các dòng tiếp: ghi dãy con tìm được và chỉ số những phần tử được chọn vào dãy con đó.

Cách giải:

Bổ sung vào A hai phần tử: a₀ = -¥ và a_n+1 = +¥. Khi đó dãy con đơn điệu tăng dài nhất chắc chắn sẽ bắt đầu từ a₀ và kết thúc ở a_n+1.

Với " i: 0 £ i £ n + 1. Ta sẽ tính L[i] = độ dài dãy con đơn điệu tăng dài nhất bắt đầu tại a_i.

1. Cơ sở quy hoạch động (bài toán nhỏ nhất):

L[n + 1] = Độ dài dãy con đơn điệu tăng dài nhất bắt đầu tại a_n+1 = +¥. Dãy con này chỉ gồm mỗi một phần tử (+¥) nên L[n + 1] = 1.

2. Công thức truy hồi:

Giả sử với i chạy từ n về 0, ta cần tính L[i]: độ dài dãy con tăng dài nhất bắt đầu tại a_i. L[i]

được tính trong điều kiện L[i + 1], L[i + 2], …, L[n + 1] đã biết:

Dãy con đơn điệu tăng dài nhất bắt đầu từ a_i sẽ được thành lập bằng cách lấy a_i ghép vào đầu một trong số những dãy con đơn điệu tăng dài nhất bắt đầu tại vị trí a_j đứng sau a_i. Ta sẽ chọn dãy nào để ghép a_i vào đầu? Tất nhiên là chỉ được ghép a_i vào đầu những dãy con bắt đầu tại a_j nào đó lớn hơn a_i (để đảm bảo tính tăng) và dĩ nhiên ta sẽ chọn dãy dài nhất để ghép a_i vào đầu (để đảm bảo tính dài nhất). Vậy L[i] được tính như sau: Xét tất cả các chỉ số j trong khoảng từ i + 1 đến n + 1 mà a_j > a_i, chọn ra chỉ số jmax có L[jmax] lớn nhất. Đặt L[i] := L[jmax] + 1.

3. Truy vết

Tại bước xây dựng dãy L, mỗi khi gán L[i] := L[jmax] + 1, ta đặt T[i] = jmax. Để lưu lại rằng: Dãy con dài nhất bắt đầu tại a_i sẽ có phần tử thứ hai kế tiếp là a_jmax.

Sau khi tính xong hay dãy L và T, ta bắt đầu từ 0. T[0] là phần tử đầu tiên được chọn, T[T[0]] là phần tử thứ hai được chọn,

T[T[T[0]]] là phần tử thứ ba được chọn …Quá trình truy vết có thể diễn tả như sau:

Ví dụ: với A = (5, 2, 3, 4, 9, 10, 5, 6, 7, 8). Hai dãy L và T sau khi tính sẽ là:

Tính toán và truy vết

 

Nhận xét: Công thức truy hồi tính các L[.] có thể tóm tắt là:

và để tính hết các L[.], ta phải mất một đoạn chương trình với độ phức tạp tính toán là O(n²). Ta có thể cải tiến cách cài đặt để được một đoạn chương trình với độ phức tạp tính toán là O(nlogn) bằng kỹ thuật sau:

Với mỗi số k, ta gọi StartOf[k] là chỉ số x của phần tử a[x] thoả mãn: dãy đơn điệu tăng dài nhất bắt đầu từ a[x] có độ dài k. Nếu có nhiều phần tử a[.] cùng thoả mãn điều kiện này thì ta chọn phần tử a[x] là phần tử lớn nhất trong số những phần tử đó. Việc tính các giá trị StartOf[.] được thực hiện đồng thời với việc tính các giá trị L[.] bằng phương pháp sau:

Khi bắt đầu vào một lần lặp với một giá trị i, ta đã biết được:

m: Độ dài dãy con đơn điệu tăng dài nhất của dãy a_i+1, a_i+2, …, a_n+1

StartOf[k] (1 £ k £ m): Phần tử a_StartOf[k] là phần tử lớn nhất trong số các phần tử a_i+1, a_i+2, …, a_n+1 thoả mãn: Dãy con đơn điệu tăng dài nhất bắt đầu từ a_StartOf[k] có độ dài k. Do thứ tự tính toán được áp đặt như trong sơ đồ trên, ta dễ dàng nhận thấy rằng: a_StartOf[k] < a_{StartOf[k - 1]}<…<aStartOf[1].

Điều kiện để có dãy con đơn điệu tăng độ dài p+1 bắt đầu tại a_i chính là a_StartOf[p] > a_i (vì theo thứ tự tính toán thì khi bắt đầu một lần lặp với giá trị i, a_StartOf[p] luôn đứng sau a_i). Mặt khác nếu đem a_i ghép vào đầu dãy con đơn điệu tăng dài nhất bắt đầu tại a_StartOf[p] mà thu được dãy tăng thì đem a_i ghép vào đầu dãy con đơn điệu tăng dài nhất bắt đầu tại a_{StartOf[p - 1]} ta cũng thu được dãy tăng. Vậy để tính L[i], ta có thể tìm số p lớn nhất thoả mãn a_StartOf[p] > a_i bằng thuật toán tìm kiếm nhị phân rồi đặt L[i] := p + 1 (và sau đó T[i] := StartOf[p], tất nhiên)