Longest Increasing Subsequence 2
Given an array of
nintegers, 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.
The first line of the input contains a single integer
n(1 ≤ n ≤ 100 000), the length of the array.
The second line contains
(), representing the elements of the array.
The program should print the length of the longest increasing subsequence of the array.
8 1 3 2 4 5 2 6 5
6 10 9 2 5 3 7
- In the first example, the longest increasing subsequence of the array is .
- In the second example, the longest increasing subsequence of the array is .
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB