Zero To DSAZero To DSA
Privacy Policy
Coin ChangeLongest Common Subsequence

Longest Increasing Subsequence

medium
Time: O(n log n)
Space: O(n)

Given an unsorted array of integers, find the length of the longest strictly increasing subsequence.

Constraints

  • 1 <= nums.length <= 2500

Examples

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
[2,3,7,101]
Input: nums = [0,1,0,3,2,3]
Output: 4