Introduction
The Longest Increasing Subsequence (LIS) problem asks: given an array of numbers, what is the length (or the sequence itself) of the longest subsequence such that all elements are in strictly increasing order? A subsequence does not need to be contiguous, but it must preserve the relative order of elements. LIS is a classic dynamic programming problem that appears in scheduling, patience solitaire, box-stacking, and bioinformatics. It has an intuitive O(n^2) DP solution and a much faster O(n log n) solution based on binary search over a list of 'tails' of increasing subsequences.
Cricket analogy: Finding the longest streak of a batsman's innings scores that keep strictly improving, without requiring the innings to be consecutive matches, is LIS; a slow method checks every earlier innings pair, while a fast method keeps a running list of best 'tail' scores per streak length.
Approach/Syntax
def lis_length_dp(nums):
n = len(nums)
if n == 0:
return 0
dp = [1] * n # dp[i] = length of LIS ending exactly at index i
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
def lis_length_fast(nums):
import bisect
tails = [] # tails[k] = smallest possible tail value of an increasing subsequence of length k+1
for x in nums:
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)Explanation
In the O(n^2) formulation, dp[i] represents the length of the longest increasing subsequence that ends at index i. To compute dp[i], we look at every earlier index j < i; if nums[j] < nums[i], then we could extend the subsequence ending at j by appending nums[i], giving a candidate length dp[j] + 1. Taking the maximum over all valid j (and the base case of 1, the element alone) gives dp[i]. The answer to the whole problem is the maximum value across the dp array, since the LIS can end anywhere. The O(n log n) approach instead maintains an array 'tails' where tails[k] is the smallest tail value among all increasing subsequences of length k+1 seen so far. For each new number x, we binary-search for the first position in tails that is >= x and overwrite it (or append x if it is larger than everything). This greedy replacement keeps tails as small as possible at every length, which never decreases the potential for future extensions; the final length of tails is the LIS length. Note that tails does not necessarily hold an actual valid subsequence, only correct length information.
Cricket analogy: To extend a batting streak ending at innings i, an analyst checks every earlier innings j and if the score there was lower, extends that streak by one; the faster method instead keeps a 'best possible' tails list and binary-searches to replace the first tail score >= the new score, shrinking future requirements.
Example
def lis_length_dp(nums):
n = len(nums)
if n == 0:
return 0
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
if __name__ == "__main__":
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print("dp array:", end=" ")
# Trace: dp = [1,1,1,2,2,3,4,4] -> LIS is e.g. [2,3,7,101] or [2,5,7,101]
print(lis_length_dp(nums)) # 4
import bisect
def lis_length_fast(nums):
tails = []
for x in nums:
pos = bisect.bisect_left(tails, x)
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)
print(lis_length_fast(nums)) # 4Complexity
The tabulated DP solution runs in O(n^2) time because of the nested loop over pairs (i, j), and O(n) space for the dp array. The patience-sorting / binary-search optimization reduces this to O(n log n) time: each of the n elements performs one bisect operation costing O(log n), and it uses O(n) space for the tails array. The O(n log n) version is preferred for large inputs, but the O(n^2) version is easier to extend if you also need to reconstruct the actual subsequence (by storing predecessor pointers) or count the number of distinct LIS.
Cricket analogy: The nested-loop DP that finds a batsman's best increasing run of scores costs O(n^2) time but makes it easy to also reconstruct the actual innings sequence via predecessor pointers; the O(n log n) tails method is faster but only tells you the streak's length, not which innings.
Key Takeaways
- dp[i] = length of the LIS ending at index i; answer is max(dp).
- Recurrence: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i], else dp[i] = 1.
- The O(n^2) approach is simple and supports reconstructing the actual subsequence via parent pointers.
- The O(n log n) approach maintains 'tails', the smallest possible tail for each subsequence length, using binary search.
- The 'tails' array is not itself a valid subsequence — it only tracks lengths, so reconstructing the real LIS requires extra bookkeeping.
Practice what you learned
1. In the O(n^2) DP formulation of LIS, what does dp[i] represent?
2. What is the time complexity of the binary-search based LIS algorithm?
3. In the O(n log n) approach, what does tails[k] represent?
4. Why can't the 'tails' array from the fast algorithm be directly returned as the LIS itself?
Was this page helpful?
You May Also Like
Longest Common Subsequence
Master the LCS DP recurrence for finding the longest shared subsequence between two strings in O(mn) time.
0/1 Knapsack Problem
Learn the classic 0/1 knapsack DP formulation, its O(nW) recurrence, and how to reconstruct the chosen items.
Introduction to Dynamic Programming
Learn what dynamic programming is and the two conditions — overlapping subproblems and optimal substructure — that make it applicable.