Find the Longest Increasing Subsequence
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 first line should contain one integer
k- the length of the longest increasing subsequence of the array.
The second line should contain
kspace-separated integers representing the longest subsequence itself. In case of several valid answers, you can output any of them.
8 1 3 2 4 5 2 6 5
5 1 2 4 5 6
6 10 9 2 5 3 7
3 2 5 7
In the second example, the subsequence is also a valid increasing subsequence of length 3.
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB