LeetCode 300. Longest Increasing Subsequence — Python Solution

Blind 75 — Programming & Technical Interview Questions — Explanation Series

The problem:

The explanation:

The is always the brute solution using depth-first search O(2^n). Then comes the dynamic programming solution O(n²). The is also another O(nlogn) solution that I will not explain since this is a difficult solution and probably won’t be expected in an interview. The dynamic programming solution works backwords from the end of the array to the start. The reason for this is it’s easy to calculate for the last few indices what their longest increasing subsequence is, but harder the farther back you go.

To fix that if you cache the solutions working backwards, you can use those saved calculations rather to redo the work. The caveat for this is that you can’t just use the previously calculated LIS because that may not result in the longest increasing subsequence. To solve this you must go through ALL previously calculated LIS to find the best subsequence for that particular value, hence why this problem is O(n²). Now to do determine that subsequence for every previously calculated LIS you set the current LIS to the max of itself and 1 plus the previously calculated LIS. This will guarantee the max LIS for each index in the array.