Longest Increasing Subsequence
Problem Description
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4 ([2,3,7,101] or [2,5,7,101])
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4 ([0,1,2,3])
Example 3:
Input: nums = [7,7,7,7]
Output: 1
DE Shaw Tier 3 — LC 300.
O(n^2) DP: dp[i] = max(dp[j]+1) for all j < i where nums[j] < nums[i].
O(n log n) with patience sorting: maintain 'tails' array — binary search for position of each element.
Example Test Cases
Example 1
Input: [[10,9,2,5,3,7,101,18]]
Expected: 4
Example 2
Input: [[0,1,0,3,2,3]]
Expected: 4
Example 3
Input: [[7,7,7,7]]
Expected: 1
Example 4
Input: [[1,3,6,7,9,4,10,5,6]]
Expected: 6
Run your code to see the results