Longest Increasing Subsequence
Medium1-D dynamic programming
Given an array of integers nums, return the length of its longest strictly increasing subsequence.
A subsequence keeps some of the values in their original order, not necessarily next to each other. Strictly increasing means each value is larger than the one before it, so equal values cannot both be used.
Examples
Input: nums = [5, 1, 6, 2, 3, 9] Output: 4
1, 2, 3, 9. The values do not have to be next to each other.
Input: nums = [4, 4, 4] Output: 1
Equal values do not count as increasing.
Constraints
1 ≤ nums.length ≤ 2500-10⁴ ≤ nums[i] ≤ 10⁴
Stuck?
Hint 1
Let best[i] be the longest increasing subsequence that ends at nums[i]. It extends the best one ending at some earlier, smaller value.
Hint 2
For each i, look at every j < i with nums[j] < nums[i] and take best[j] + 1. That is O(n²); keeping the smallest possible tail for each length and binary searching it makes it O(n log n).
The idea
For each length, only the smallest value that can end an increasing subsequence of that length matters, since a smaller ending leaves more room to grow. Those smallest endings are always in increasing order, so each new value finds its place among them by binary search.
Time O(n log n)Extra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
tails[k] is the smallest value that ends an increasing subsequence of length k + 1 among the values seen so far. Its length is the longest subsequence found.
function lengthOfLIS(nums) { const tails = []; for (const value of nums) { let low = 0; let high = tails.length; while (low < high) { const mid = Math.floor((low + high) / 2); if (tails[mid] < value) low = mid + 1; else high = mid; } tails[low] = value; } return tails.length;}The trap
The O(n²) table is the right idea: the best subsequence ending at nums[i] extends the best one ending at an earlier, smaller value. Writing the comparison as <= lets an equal value extend it too, which is easy to miss because arrays without repeats come out right. Any array with repeated values can get a length that is too long, since equal values are not strictly increasing.
function lengthOfLIS(nums) { const best = new Array(nums.length).fill(1); for (let i = 1; i < nums.length; i++) { for (let j = 0; j < i; j++) { if (nums[j] <= nums[i]) best[i] = Math.max(best[i], best[j] + 1); // counts equal values } } return Math.max(...best);}