Longest Increasing Subsequence
Last Updated: March 28, 2026
Understanding the Problem
We need to find the longest subsequence within the given array where each element is strictly greater than the one before it. The elements don't have to be adjacent in the original array, but they must appear in the same relative order.
This is different from the longest increasing subarray problem, where elements must be contiguous. Here, we can skip elements freely. For instance, in [10, 9, 2, 5, 3, 7, 101, 18], the subsequence [2, 3, 7, 101] picks elements at indices 2, 4, 5, and 6, skipping everything in between.
The core challenge is that choosing one element over another can have ripple effects on the rest of the subsequence. Picking a smaller value early on gives us more room to extend the sequence later. This "optimal substructure" property hints strongly at dynamic programming, and the question is how to define our subproblems efficiently.
Key Constraints:
1 <= nums.length <= 2500— With n up to 2,500, O(n^2) gives about 6.25 million operations, which is comfortable. O(n^3) would mean around 15 billion, clearly too slow.-10^4 <= nums[i] <= 10^4— Values can be negative. The range is bounded, but at 20,001 possible values, a frequency array approach is feasible but not the cleanest route.
Approach 1: Dynamic Programming
Intuition
The most natural way to approach this problem is with dynamic programming. Here is the key insight: if we know the length of the longest increasing subsequence ending at every index before the current one, we can compute the answer for the current index by looking at all previous elements that are smaller.
Define dp[i] as the length of the longest strictly increasing subsequence that ends with nums[i]. Every element on its own forms an increasing subsequence of length 1, so we initialize all dp[i] = 1.
For each index i, we scan all indices j from 0 to i-1. If nums[j] < nums[i], then we can extend whatever subsequence ended at j by appending nums[i] to it. So dp[i] = max(dp[i], dp[j] + 1).
The final answer is the maximum value across the entire dp array, since the longest increasing subsequence could end at any index.
Algorithm
- Create an array
dpof the same length asnums, initialized to all 1s. - For each index
ifrom 1 to n-1, scan all previous indicesjfrom 0 to i-1. - If
nums[j] < nums[i], updatedp[i] = max(dp[i], dp[j] + 1). - Track the overall maximum across all
dp[i]values. - Return the maximum.
Example Walkthrough
Code
- Time Complexity: O(n^2). We have two nested loops. The outer loop runs n times, and for each iteration, the inner loop runs up to i times. Total work is 1 + 2 + ... + (n-1) = n(n-1)/2, which is O(n^2).
- Space Complexity: O(n). We store a dp array of size n.
The DP approach scans all previous indices for each element, doing O(n) work per element. What if we maintained a sorted structure that lets us find the right insertion point in O(log n) instead?
Approach 2: Binary Search with Patience Sorting
Intuition
We maintain an array called tails, where tails[i] holds the smallest possible tail element of all increasing subsequences of length i + 1 found so far. This array is always sorted in increasing order, because if you have an increasing subsequence of length 3 ending in value 7, you must also have one of length 2 ending in a value less than 7.
For each new element num, if it is larger than the last element in tails, it extends the longest subsequence, so we append it. Otherwise, we find the leftmost element in tails that is greater than or equal to num and replace it. This lowers a tail value, opening up more room for future elements.
Since tails is always sorted, we can use binary search for each operation, making each step O(log n).
A key subtlety: the tails array does NOT represent an actual increasing subsequence. It is a bookkeeping tool that tracks the "best possible endings" for subsequences of each length. The length of tails at the end equals the length of the LIS.
The tails array maintains an invariant: it is always sorted, and tails[i] holds the smallest possible ending value among all increasing subsequences of length i + 1. By always keeping the tail as small as possible, we maximize the chance that future elements can extend existing subsequences.
When we replace an element in tails, we are not destroying any existing subsequence. We are just updating our bookkeeping to reflect that there is now a "better" (smaller-tailed) subsequence of that length. And when we append, the length of the longest subsequence has genuinely increased by one.
Algorithm
- Initialize an empty array
tails. - For each element
numin the input array, binary search for the leftmost position intailswheretails[pos] >= num. - If
posequals the length oftails, appendnum(new longest subsequence). - Otherwise, replace
tails[pos]withnum(improve an existing subsequence's tail). - Return the length of
tails.
Example Walkthrough
Code
- Time Complexity: O(n log n). We iterate through all n elements once. For each element, we perform a binary search on the tails array, which has at most n elements. Binary search is O(log n), so total is O(n log n).
- Space Complexity: O(n). The tails array can grow up to size n in the worst case (when the input is already sorted).