Longest Strictly Rising Subsequence
Given daily readings nums, find the longest subsequence (elements kept in their original order, not necessarily adjacent) in which every element is strictly greater than the one before it. Return its length.
An O(n²) dynamic programme works for small inputs; the large tests need the O(n log n) method that keeps, for each length, the smallest possible tail value.
Example 1
Input: nums = [4,10,4,3,8,9] Output: 3 Explanation: For example 3, 8, 9.
Example 2
Input: nums = [0,1,0,3,2,3] Output: 4 Explanation: 0, 1, 2, 3.
Constraints
- 0 <= nums.length <= 3 * 10^4
- -10^5 <= nums[i] <= 10^5
Hint 1
Keep an array tails where tails[L] is the smallest value that can end a rising subsequence of length L + 1.
Hint 2
For each number, binary search the first tail that is >= it and replace it (or append).
Discussion 0
Join free to post in the discussion.
Good practice for: Data Scientist, Machine Learning Engineer, Backend Developer, Data Engineer, Full Stack Developer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.