Longest Increasing Subsequence
Mediumjavapythonccppjavascript
Given an integer array, find the length of the longest subsequence in which each element is strictly greater than the previous one.
Input Format
The first line contains an integer N. The second line contains N space-separated integers.
Output Format
Print the length of the longest strictly increasing subsequence.
Example 1
Input
8 10 9 2 5 3 7 101 18
Output
4
Explanation: One longest increasing subsequence is [2, 3, 7, 101].
- 1 <= N <= 100000
- -1000000000 <= A[i] <= 1000000000