TopCoder

User's AC Ratio

95.4% (83/87)

Submission's AC Ratio

47.1% (129/274)

Tags

Description

給你長度為N的一個正整數序列,請你求出最長嚴格遞增子序列的長度。
所謂嚴格遞增子序列,是指去掉序列中的某些數字之後,剩下的子序列是嚴格遞增的。

Input Format

第一列有一個正整數N,(1<=N<=100,000)
第二列有N個以空白隔開的正整數。

Output Format

輸出LIS的長度。

Sample Input

10
1 3 2 4 6 5 7 8 10 9

Sample Output

7

Hints

※額外的測試中:
  總共至少有30%的測試資料 N<=10
  總共至少有60%的測試資料 N<=1,000

Problem Source

原TIOJ1175 / TIOJ Contest #1020。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144