How to Find the Longest Increasing Subsequence
This problem was asked by Microsoft.
Given an array of numbers, find the length of the longest increasing subsequence in the array. The subsequence does not necessarily have to be contiguous.
For example, given the array [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], the longest increasing subsequence has length 6: it is 0, 2, 6, 9, 11, 15.
This naive, brute force way to solve this is to generate each possible subsequence, testing each one for monotonicity and keeping track of the longest one. That would be prohibitively expensive: generating each subsequence already takes O(2^N)!
Instead, let’s try to tackle this problem using recursion and then optimize it with dynamic programming.
Assume that we already have a function that gives us the length of the longest increasing subsequence. Then we’ll try to feed some part of our input array back to it and try to extend the result. Our base cases are: the empty list, returning 0, and an array with one element, returning 1.
- For every index
iup until the second to last element, calculate
longest_increasing_subsequenceup to there.
- We can only extend the result with the last element if our last element is greater than
arr[i](since otherwise, it’s not increasing).
- Keep track of the largest result.
This is really slow due to repeated subcomputations (exponential in time). So, let’s use dynamic programming to store values to recompute them for later.
We’ll keep an array
A of length N, and
A[i] will contain the length of the longest increasing subsequence ending at
i. We can then use the same recurrence but look it up in the array instead:
This now runs in O(N^2) time and O(N) space.
Are you interviewing for programming jobs, or do you just enjoy fun programming questions? Check out our newsletter, Daily Coding Problem, to get a question in your inbox every day.
Ace your programming interview
Get a coding problem every day in your inbox!