hardCodingMidSeniorStaff
Find the length of the longest strictly increasing subsequence, then get it under quadratic time.
6 min readUpdated 2026-08-15
Answer
Short answer
The quadratic dynamic programme asks for the best chain ending at each index. The faster version keeps one array where slot j holds the smallest possible tail of an increasing subsequence of length j plus one; that array stays sorted, so each element is placed by binary search for O of n log n.
Was this answer helpful?
Likely follow-ups
- Return the subsequence itself, not just its length.
- What single character changes if the subsequence may be non-decreasing?
- Why does Arrays.binarySearch not give you the index you need here?
- How many pairs of numbers can you nest inside each other, given a list of width and height pairs?
Related questions
- Envelopes nest only when both width and height are strictly larger. How many can you nest, and why must equal widths be sorted by height descending?hardAlso on longest-increasing-subsequence and binary-search4 min
- Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra give the wrong answer?mediumAlso on dynamic-programming5 min
- Given package weights in a fixed order, find the smallest ship capacity that delivers them all within D daysmediumAlso on binary-search5 min
- You are given a sorted array that has been rotated by an unknown amount. Find a target value in logarithmic time.mediumAlso on binary-search5 min