Longest Increasing Subsequence 1
Given an array of
n integers, you are asked to find the longest increasing subsequence of the array. If there are multiple such subsequences you can output any of them.A subsequence of an array is obtained by deleting some (possibly zero) elements of the array, without changing the order of the remaining elements. For example, if the array is , then is a subsequence of , but is not a subsequence of , since the order of the elements is not preserved.
💡
An increasing subsequence of an array is a subsequence in which the elements are in increasing order. For example, if the array is , then is an increasing subsequence of , but is not an increasing subsequence of , since the elements are not in increasing order.
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ 1000), the length of the array.The second line contains
n space-separated integers Output
The program should print the length of the longest increasing subsequence of the array.
Examples
Input | Output |
8
1 3 2 4 5 2 6 5 | 5 |
6
10 9 2 5 3 7 | 3 |
Explanation
- In the first example, the longest increasing subsequence of the array is .
- In the second example, the longest increasing subsequence of the array is .
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB