Longest Increasing Subsequence
The problem
Return the length of the longest strictly increasing subsequence of an integer array. Chosen elements keep their order but need not be adjacent.
Example
[4, 10, 5, 6, 2, 8] → 4, from [4, 5, 6, 8]
Need a hint?
Keep the smallest possible tail for each achievable subsequence length.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Maintain sorted tails. For each value x, binary-search the first tail ≥ x and replace it, or append if none exists. Smaller tails leave more room for future values. The tails list gives the correct length, although its final contents need not form one input subsequence.
Complexity
O(n log n) time and O(n) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.