Longest Increasing Subsequence

Dynamic Programming + Binary Search

1:00

Two algorithms for finding the longest strictly increasing subsequence — an intuitive O(n²) dynamic programming solution and an O(n log n) approach using a sorted tails array with binary search.

By the end, you can

Distinguish a subsequence from a subarray and explain why gaps are permitted in LIS.
Derive the O(n²) DP recurrence and fill the dp table by hand for a small array.
Explain why the answer is max(dp), not dp[last].
Describe the patience-sorting card-game analogy and explain why pile count equals LIS length.
Trace the tails algorithm on a small array, identifying append vs replace decisions at each step.
Explain why the tails array stays sorted and how that enables binary search.
Recognise that tails values are bookkeeping and explain how to reconstruct the actual LIS elements.
State the time and space complexity of both approaches and choose the right one for a given context.
Identify when to use bisect_left versus bisect_right depending on whether the problem demands strict or non-decreasing increase.

Up next in String Algorithms, Advanced DP & Competitive Techniques