Longest Increasing Subsequence
Problem
Return the length of the longest strictly increasing subsequence (not necessarily contiguous). The O(n log n) solution is the expected follow-up.
Example 1
Input: [10, 9, 2, 5, 3, 7, 101, 18] Output: 4
[2, 3, 7, 101].
Test cases
Case 1
Input: [10,9,2,5,3,7,101,18] Expected: 4
Case 2
Input: [0,1,0,3,2,3] Expected: 4
Case 3
Input: [7,7,7,7] Expected: 1
View solutionHide solution2 approaches
1. DP O(n²)
Time O(n²)Space O(n)
dp[i] = longest increasing subsequence ending at i = 1 + max(dp[j]) for j<i with nums[j]<nums[i].
function lengthOfLIS(nums) { const dp = Array(nums.length).fill(1); let best = 1; for (let i = 1; i < nums.length; i++) { for (let j = 0; j < i; j++) if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1); best = Math.max(best, dp[i]); } return best;}2. Patience sorting + binary search
Time O(n log n)Space O(n)
Maintain `tails`, where tails[k] is the smallest possible tail of an increasing subsequence of length k+1. Binary-search the insert point.
function lengthOfLIS(nums) { const tails = []; for (const x of nums) { let lo = 0, hi = tails.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (tails[mid] < x) lo = mid + 1; else hi = mid; } tails[lo] = x; } return tails.length;}