1175 . Longest Increasing Subsequence

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

93.5% (290/310)

Submission's AC Ratio

43.6% (459/1052)

Tags

TIOJcon

Description

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

Input Format

第一列有一個正整數 N（1≤N≤105）
第二列有 N 個以空白隔開的正整數。

Output Format

輸出 LIS 的長度。

Sample Input 1

10
1 3 2 4 6 5 7 8 10 9

Sample Output 1

7

Hints

※額外的測試中：
　　總共至少有 30% 的測試資料 N≤10
　　總共至少有 60% 的測試資料 N≤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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10
10 1000 65536 262144 11
Submit
Back to Top