Longest Increasing Subsequence (最長増加部分列) 1
与えられたのは、
n 個の整数からなる配列です。この配列に対して、最長の増加部分列を見つけることが求められています。もし同じ長さの最長増加部分列が複数存在するなら、そのうちどれを出力しても構いません。配列の部分列とは、元の順序を崩さずにいくつかの要素（0 個以上）を削除して得られるものを指します。たとえば、配列 において、 は の部分列ですが、 は要素の順番が維持されていないため、この配列の部分列ではありません。
💡
増加部分列とは、取り出した要素が厳密に昇順になっている部分列を指します。たとえば、配列 において、 は増加部分列ですが、 は要素が昇順ではないため、増加部分列ではありません。
入力 (Input)
最初の行には、配列の長さを表す整数
n (1 ≤ n ≤ 1000) が与えられます。次の行には、配列の要素を表す () が空白区切りで並びます。
出力 (Output)
配列の最長増加部分列の長さを出力してください。
Examples
Input | Output |
8
1 3 2 4 5 2 6 5 | 5 |
6
10 9 2 5 3 7 | 3 |
Explanation
- 最初の例では、配列の最長増加部分列として が得られます。
- 二番目の例では、最長増加部分列として が得られます。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB