Longest Increasing Subsequence
Given an array of integers, find the length of the longest subsequence whose elements appear in strictly increasing order. A subsequence keeps the relative order of the array but does not have to be contiguous.
Input & Output
Input
nums — the integer sequence
Output
the length of the longest strictly increasing subsequence of nums
Example
Input
nums = [50, 3, 10, 7, 40, 80]
Output
4
Explanation
[3, 7, 40, 80] increases at every step and uses four elements. [3, 10, 40, 80] is another subsequence of the same length, so the answer is the length rather than the subsequence itself.
Example
Input
nums = [1, 2, 4, 3]
Output
3
Explanation
Both [1, 2, 4] and [1, 2, 3] are longest increasing subsequences which have length 3.
Example
Input
nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output
4
Explanation
[2, 3, 7, 101] and [2, 5, 7, 18] both reach length 4. Nothing longer exists because the leading 10, 9 cannot extend any of them.
Constraints
0 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4