Mô tả và yêu cầu

Dãy con tăng dài nh ấ t (b ả n d ễ )

Cho m ột dãy s ố nguy ên gồ m N phầ n t ử A [ 1] , A [ 2] , . . . A [ N] .
B iết rằ ng dãy c on t ăng đơn đi ệu là 1 dãy A [ i 1] , . . . A [ ik] t hỏa mãn
i1 < i2 < . . . < ik v à A [ i1] < A [ i2] < . . < A [ ik] . Hãy c ho biết dãy c on t ăng đơn điệu dài nhất của dãy này c ó bao nhiêu
phần t ử?

Dữ liệu vào

Dòng 1 gồ m 1 s ố nguy ên là s ố N (1 ≤ N ≤ 1000).
Dòng t hứ 2 ghi N s ố nguy ên A [ 1] , A [ 2] , . . A [ N] (1 ≤ A [ i] ≤ 10000).

O utput

Ghi ra độ dài c ủa dãy c on t ăng đơ n đi ệu dài nhất .

Ví dụ

I nput:
6
1  2  5  4  6  2

Output:
4

Gi  ả i   thí ch  test  ví   d    ụ:  Dãy   c on  dài  nhất   là  dãy   A [ 1]   =   1  <   A [ 2]   =   2  <   A [ 4]   =   4  <   A [ 5]   =   6,   độ  dài  dãy   này   là  4.

Gợ   i   ý:  S ử  dụng  phương  pháp  Quy   Hoạ                     c h  Động.   F[ i] :   Độ  dài  dãy   c on  đơ            n  đi ệu  t ăng  dài  nhất   mà  phần  t              ử  c uối  c ùng  là
s ố   A [ i]   này .