題目描述

給定一個由正整數組成的序列，求出它的最長上升子序列的長度。上升子序列是指在原序列中保持相對順序的一個子序列，且每個元素都比前一個元素大，例如1,3,5,7是一個上升子序列，而1,2,4,3不是。 輸入：第一行是一個正整數n，表示序列的長度。接下來一行有n個正整數，表示序列的元素。 輸出：一個正整數，表示最長上升子序列的長度。 限制：1 <= n <= 1000，1 <= 元素 <= 1000 範例： 輸入： 8 10 9 2 5 3 7 101 18 輸出： 4 解釋： 最長上升子序列是2,3,7,101，長度為4。

輸入格式

第一行是一個正整數n，表示序列的長度。接下來一行有n個正整數，表示序列的元素。

輸出格式

一個正整數，表示最長上升子序列的長度。

限制：1 <= n <= 1000，1 <= 元素 <= 1000。

Samples

8
10 9 2 5 3 7 101 18

4

原始資料

• Zero1 題號：b051
• Hydro 題號：Z1051
• Locale：zh_TW
• Display：open