Longest Increasing Subsequence
DSA · Dynamic Programming
Theory
The longest increasing subsequence (LIS) is the longest sequence of elements taken from an array, in their original order but not necessarily adjacent, where each element is larger than the previous one. For [10, 9, 2, 5, 3, 7, 101, 18] one LIS is [2, 3, 7, 18], so the answer is 4. The DP solution sets dp[i] to the length of the longest increasing subsequence ending at index i and checks every earlier j with a smaller value: dp[i] = 1 + max(dp[j]). That takes O(n^2). A smarter O(n log n) method keeps an array tails where tails[k] is the smallest possible last value of an increasing subsequence of length k + 1, and uses binary search to place each new number.
Why we use it
LIS is a classic interview problem that shows both a straightforward DP and an optimisation with binary search. It models problems like nesting boxes, scheduling and stacking.
When to use it
Use the O(n^2) DP for small inputs or when you need to reconstruct the subsequence easily; use the binary search version for large arrays.
How it works
- tails = []
- For each x
- i = position of x in tails (binary search)
- i == len(tails)? Yes: Append x. No: Replace tails[i] with x.
- Length = len(tails)
Syntax
DP: dp[i] = 1 + max(dp[j] for j < i if a[j] < a[i]) O(n^2)
Tails: bisect_left(tails, x) per element O(n log n)Example
from bisect import bisect_left
nums = [10, 9, 2, 5, 3, 7, 101, 18]
# O(n^2) DP with reconstruction
n = len(nums)
dp, prev = [1] * n, [-1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
dp[i], prev[i] = dp[j] + 1, j
end = max(range(n), key=lambda i: dp[i])
seq = []
while end != -1:
seq.append(nums[end]); end = prev[end]
print("dp:", dp)
print("LIS:", seq[::-1], "length", len(seq))
# O(n log n) with binary search
tails = []
for x in nums:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
print(f"after {x:>3}: tails = {tails}")
print("Length:", len(tails))Key points
- Subsequence keeps order but allows gaps
- O(n^2) DP is simple and can rebuild the sequence
- Tails + binary search gives O(n log n)
- tails is not itself the LIS, only its length is guaranteed