(8 ĐIỂM) DÃY CON TĂNGCHO DÃY SỐ NGUYÊN A = A1, A2, …, AN. (N ≤ 10000,...

Bài 3 : (8 điểm)

Dãy con tăng

Cho dãy số nguyên A = a

1

, a

2

, …, a

n

. (n ≤ 10000, -10000 ≤ ai ≤ 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, 8). Dãy con đơn điệu tăng dài nhất là: (1, 2, 3, 4, 5, 6, 7, 8).Dữ liệu (Input) vào từ file văn bản SEQ.INPVí dụ: • Dòng 1: Chứa số nSEQ.INP SEQ.OUT• Dòng 2: Chứa n số a

1

, a

2

, …, a

n

cách nhau ít

9

nhất một dấu cách

a[1]=1

1 2 8 5 6 7 12 10 11

7

Kết quả (Output) ghi ra file văn bản SEQ.OUT

a[2]=2

a[4]=5

• Dòng 1: Ghi độ dài dãy con tìm được

a[5]=6

• Các dòng tiếp: ghi dãy con tìm được và chỉ số

a[6]=7

những phần tử được chọn vào dãy con đó.

a[8]=10

a[9]=11