Return the length of the longest strictly increasing subsequence
A ride-sharing dashboard plots a driver’s rating after every trip. Product wants a “longest improvement streak” badge: the most ratings you can pick, in trip order, so that each picked rating is higher than the previous picked one. The picked trips do not have to be next to each other.
Implement longestRisingLength(nums). It returns the length of the longest strictly increasing subsequence of nums.
longestRisingLength(nums) // => number
longestRisingLength([7, 2, 8, 1, 3, 4, 10, 6]);
// => 4 (for example 2, 3, 4, 10 or 1, 3, 4, 6)
longestRisingLength([4, 10, 4, 3, 8, 9]);
// => 3 (4, 8, 9)
longestRisingLength([5, 5, 5]);
// => 1 (equal values are not rising)
longestRisingLength([9, 7, 4, 1]);
// => 1
longestRisingLength([]);
// => 0
nums contains finite numbers, which can be negative, zero, or fractional.nums.The classic dynamic programming solution is O(n²). Can you reach O(n log n)?