1. Introduction
The Longest Increasing Subsequence (LIS) problem is a classic algorithmic challenge: given a sequence of numbers, find the longest subsequence in which elements are in strictly increasing order. The elements need not be contiguous in the original sequence, only their relative order must be preserved.
"The patience sorting algorithm for LIS connects a simple card game to a deep mathematical result about the longest increasing subsequence of a random permutation." -- David Aldous and Persi Diaconis
The LIS problem is notable for having two well-known solutions: a straightforward O(n^2) dynamic programming approach and a more sophisticated O(n log n) algorithm that uses binary search. Understanding both provides valuable insight into algorithm optimization techniques.
2. Problem Definition
Input: An array A of n integers.
Output: The length of the longest strictly increasing subsequence.
| Input Array | LIS | Length |
|---|---|---|
| [10, 9, 2, 5, 3, 7, 101, 18] | [2, 3, 7, 18] or [2, 5, 7, 18] | 4 |
| [0, 1, 0, 3, 2, 3] | [0, 1, 2, 3] | 4 |
| [7, 7, 7, 7] | [7] | 1 |
3. Brute Force Approach
The brute force approach generates all 2^n subsequences of the array, filters those that are strictly increasing, and returns the length of the longest one. This has exponential time complexity.
functionlisBrute(A, n, prev, curr): if curr == n: return0// Option 1: skip current element skip = lisBrute(A, n, prev, curr + 1) // Option 2: include current element if it extends the subsequence take = 0if prev == -1or A[curr] > A[prev]: take = 1 + lisBrute(A, n, curr, curr + 1) returnmax(skip, take)4. Optimal Substructure
The LIS ending at position i can be constructed by extending the LIS ending at some earlier position j (where j < i and A[j] < A[i]). The optimal LIS ending at i extends the longest such LIS among all valid predecessors.
Overlapping subproblems occur because the LIS ending at position j may be needed when computing the LIS for multiple later positions.
5. Recurrence Relation
Let dp[i] represent the length of the longest increasing subsequence ending at index i.
Recurrence:dp[i] = 1 + max(dp[j]) for all j < i where A[j] < A[i]
If no such j exists, then dp[i] = 1 (the element itself forms a subsequence of length 1).
Answer:max(dp[0], dp[1], ..., dp[n-1])
6. O(n^2) DP Solution
functionlisDP(A): n = length(A) dp = array of size n, filled with 1for i = 1to n-1: for j = 0to i-1: if A[j] < A[i]: dp[i] = max(dp[i], dp[j] + 1) returnmax(dp) For each element at index i, we look at all previous elements j < i. If A[j] < A[i], we can extend the LIS ending at j by appending A[i]. We take the maximum over all such extensions.
7. Worked Example (O(n^2))
Array: A = [3, 1, 4, 1, 5, 9, 2, 6]
| Index i | A[i] | Valid predecessors (j where A[j] < A[i]) | dp[i] |
|---|---|---|---|
| 0 | 3 | None | 1 |
| 1 | 1 | None | 1 |
| 2 | 4 | j=0 (A[0]=3, dp=1), j=1 (A[1]=1, dp=1) | 2 |
| 3 | 1 | None | 1 |
| 4 | 5 | j=0 (dp=1), j=1 (dp=1), j=2 (dp=2), j=3 (dp=1) | 3 |
| 5 | 9 | j=0 (dp=1), j=1 (dp=1), j=2 (dp=2), j=3 (dp=1), j=4 (dp=3) | 4 |
| 6 | 2 | j=1 (dp=1) | 2 |
| 7 | 6 | j=0 (dp=1), j=1 (dp=1), j=2 (dp=2), j=3 (dp=1), j=4 (dp=3), j=6 (dp=2) | 4 |
The LIS length is max(dp) = 4. One valid LIS is [1, 4, 5, 9] (indices 1, 2, 4, 5). Another is [1, 4, 5, 6] (indices 1, 2, 4, 7) or [3, 4, 5, 6] (indices 0, 2, 4, 7).
8. O(n log n) with Binary Search
The key insight for the O(n log n) algorithm is to maintain an array tails where tails[k] holds the smallest possible tail element for an increasing subsequence of length k+1. This array is always sorted, enabling binary search.
functionlisOptimal(A): n = length(A) tails = [] // Dynamic arrayfor i = 0to n-1: // Binary search for the position to replace pos = lowerBound(tails, A[i]) if pos == length(tails): tails.append(A[i]) // Extend longest subsequenceelse: tails[pos] = A[i] // Replace to keep smallest tailreturnlength(tails)Why does this work? The tails array maintains the invariant that tails[k] is the smallest value that can end an increasing subsequence of length k+1. By keeping these tails as small as possible, we maximize the chance that future elements can extend the subsequence. The binary search finds the correct position in O(log n) time.
Important: The tails array does NOT represent an actual LIS. It is a bookkeeping structure used only to determine the LIS length. To reconstruct the actual subsequence, additional predecessor tracking is required.
9. Worked Example (O(n log n))
Array: A = [3, 1, 4, 1, 5, 9, 2, 6]
| Step | A[i] | Action | tails after |
|---|---|---|---|
| 1 | 3 | Append (tails empty) | [3] |
| 2 | 1 | Replace tails[0] (1 < 3) | [1] |
| 3 | 4 | Append (4 > 1) | [1, 4] |
| 4 | 1 | Replace tails[0] (1 = 1, lowerBound finds pos 0) | [1, 4] |
| 5 | 5 | Append (5 > 4) | [1, 4, 5] |
| 6 | 9 | Append (9 > 5) | [1, 4, 5, 9] |
| 7 | 2 | Replace tails[1] (2 < 4) | [1, 2, 5, 9] |
| 8 | 6 | Replace tails[2] (6 > 5 but < 9) | [1, 2, 6, 9] |
Final tails length is 4, confirming the LIS length. Note again that [1, 2, 6, 9] is not itself a valid LIS from the original array -- it is the bookkeeping structure. A valid LIS is [1, 4, 5, 9].
10. Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force | O(2^n) | O(n) |
| O(n^2) DP | O(n^2) | O(n) |
| O(n log n) Binary Search | O(n log n) | O(n) |
The O(n log n) algorithm processes each element once (O(n)) and performs a binary search on the tails array for each element (O(log n)), giving the overall O(n log n) time complexity. This is optimal for comparison-based algorithms.
11. Variations
Longest Non-Decreasing Subsequence
Change the condition from strictly increasing (A[j] < A[i]) to non-decreasing (A[j] <= A[i]). In the binary search approach, use upperBound instead of lowerBound.
Longest Decreasing Subsequence
Reverse the array and compute the LIS, or reverse the comparison in the algorithm.
Number of Distinct LIS
Count the number of longest increasing subsequences of maximum length. This requires an additional array tracking the count of LIS ending at each position.
Minimum Number of Decreasing Subsequences
By Dilworth's theorem, the minimum number of non-increasing subsequences that partition the array equals the LIS length. This has applications in scheduling theory.
12. Applications
- Patience sorting: The O(n log n) LIS algorithm is equivalent to the patience sorting card game, which also determines the number of piles needed.
- Box stacking: Determining the maximum height of stackable boxes (where each dimension must be strictly smaller) reduces to LIS in sorted order.
- Sequence alignment: LIS appears in certain bioinformatics problems involving ordered gene sequences.
- Version control: Finding the longest sequence of lines that appear in the same order in two file versions.
- Scheduling: Chain decomposition problems in partially ordered sets relate to LIS via Dilworth's theorem.
13. References
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms (4th ed.). MIT Press, 2022.
- Fredman, M. L. "On computing the length of longest increasing subsequences." Discrete Mathematics, 11(1):29-35, 1975.
- Aldous, D. and Diaconis, P. "Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem." Bulletin of the AMS, 36(4):413-432, 1999.
- Knuth, D. E. The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley, 1998.