LIS - Dãy con tăng dài nhất
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.5 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Tìm dãy con không nhất thiết là liên tiếp, có độ dài cực đại của một dãy cho trước mà các phần tử của dãy con được sắp xếp theo trật tự giá trị tăng dần. Ví dụ, độ dài của LIS của dãy {10, 22, 9, 33, 21, 50, 41, 60, 80 } là 6 và LIS ={10, 22, 33, 50, 60, 80}.

Dữ liệu vào:

- Dòng đầu chứa số nguyên dương n (n ≤ 104)

- n dòng sau, mỗi dòng chứa 1 số nguyên thuộc dãy số.

Kết quả ra: In ra độ dài dãy con dài nhất như yêu cầu

Ví dụ

  • input
    11
    1
    2
    1
    3
    2
    4
    3
    6
    4
    5
    6
    output
    6
Back to Top