1175 . Longest Increasing Subsequence
TopCoder
Tags
Description
給你長度為 $N$ 的一個正整數序列，請你求出最長嚴格遞增子序列的長度。
所謂嚴格遞增子序列，是指去掉序列中的某些數字之後，剩下的子序列是嚴格遞增的。
Input Format
第一列有一個正整數 $N$（$1 \le N \le 10 ^ 5$）
第二列有 $N$ 個以空白隔開的正整數。
Output Format
輸出 LIS 的長度。
Sample Input 1
10
1 3 2 4 6 5 7 8 10 9
1 3 2 4 6 5 7 8 10 9
Sample Output 1
7
Hints
※額外的測試中：
總共至少有 30% 的測試資料 $N \le 10$
總共至少有 60% 的測試資料 $N \le 1000$
Problem Source
原TIOJ1175 / TIOJ Contest #1020。Problem Setter：Tmt。
2020.03.10 Update: Added $\LaTeX$ by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |