Hard · DP + Binary Search
Understand → Visualise → Practice.
For each subsequence length, a smaller ending value leaves more room to extend later. Binary search finds which tail a new value improves.
tails[i] is the smallest known final value of an increasing subsequence of length i + 1.
Find the first tail ≥ value.
Replace that tail, or append if none exists.
tails.length equals the LIS length.
O(n log n) time and O(n) space.
The tails array is not necessarily an actual subsequence; it stores the best tail value for each length.
Read the full guide first: Dynamic Programming.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.