96. Longest Increasing Subsequence

Longest Increasing Subsequence

題目敘述

求Longest Increasing Subsequence

輸入說明

有多筆測資，測資的第一行有一個數字$N$，表示數列有$N$個數字，下一行有$N$個數字，表示該數列，每個數字皆在$int$可以表達的範圍內。

保證：

• $1\leq N \leq 100000$

輸出說明

針對每組測資輸出一行，為LIS(嚴格遞增)的長度。

範例輸入

6
2 3 7 5 6 8
8
2 4 5 6 3 4 5 6

範例輸出

5
5

配分:

配分	限制
10%	$n \leq 10$
40%	$n \leq 1000$
50%	$n \leq 30000$
時限	100ms
記憶體	150000 bytes

Judge Setting

run-time limit: 100 ms
memory limit: 15000000 byte
測資數量: 0