Longest Increasing Subsequence
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.
Choosing one element over another affects how far the subsequence can extend later. Picking a smaller value early leaves more room to add elements afterward. The answer to a subproblem (the longest subsequence ending at some index) is built from answers to smaller subproblems, which points toward dynamic programming. The remaining question is how to define those subproblems so they can be computed efficiently.
Key Constraints:
1 <= nums.length <= 2500: With n up to 2,500, an O(n^2) solution does about 6.25 million operations, which runs well within typical time limits. This is the bound that makes the quadratic DP acceptable.-10^4 <= nums[i] <= 10^4: Values can be negative, so any approach must handle negative numbers correctly. All values fit comfortably in a 32-bit integer, and the longest possible answer is 2,500, so no overflow concerns arise.
Approach 1: Dynamic Programming
Intuition
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 and extending the best of them.
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. The next approach replaces that linear scan with a binary search over a sorted structure, cutting the per-element cost to O(log n).
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 found so far, so we append it. Otherwise, we find the leftmost element in tails that is greater than or equal to num and replace it with num. Replacing lowers that tail value, which leaves more room for future elements to extend the subsequence of that length.
Since tails is always sorted, each lookup is a binary search, making every step O(log n).
The tails array does not represent an actual increasing subsequence at any given moment. Its values can come from different positions in the input. It is a bookkeeping structure that tracks the smallest achievable ending value for a subsequence of each length, and its final length equals the length of the LIS.
The invariant is that after processing any prefix of the input, tails[i] holds the smallest possible ending value among all increasing subsequences of length i + 1 within that prefix, and tails stays sorted. A smaller tail for a given length never reduces what can be built later, since any future element that could extend a subsequence ending at a larger value can also extend one ending at a smaller value.
A replacement at position pos does not destroy a real subsequence. It records that a subsequence of length pos + 1 now exists with an ending value of num, which is no larger than the previous tails[pos]. An append happens only when num exceeds every tail, which means a subsequence one longer than any seen so far now exists. So the final length of tails equals the length of the longest increasing subsequence.
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).