Gọi f[i] là vị trí của phần tử tận cùng nhỏ nhất của dãy con tăng độ dài i. Khi đó mảng f[] là một dãy con tăng khi duyệt từ đầu dãy đến cuối dãy ban đầu (do lưu vị trí và cập nhật). Khi xét đến một phần tử i thì ta chặt nhị phân tìm dãy có độ dài j dài nhất sao cho phần tử tận cùng của dãy này có giá trị nhỏ hơn phần tử đang xét, tức là tìm j max sao cho a[i] > a[f[j]]. Sau đó chỉ việc cập nhật lại mảng f[] với phần tử mới tại vị trí i.
Problem
https://vn.spoj.com/problems/LIS
https://oj.vnoi.info/problem/LIS
(Giống bài LIQ) Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con tăng dài nhất trong dãy đó. In ra số lượng phần tử của dãy con. Các số trong phạm vi longint.
Input
- Dòng đầu tiên gồm số nguyên N.
- Dòng thứ hai gồm N số mô tả dãy.
Output
Gồm một số nguyên duy nhất là đáp số của bài toán
Example
Input
5
2 1 4 3 5
Output
3
Tutorial
Submission
LIS.cpp