Overview
Finding the length of the LIS is standard O(N²). But if you want to know *which* elements make up the sequence, you need to track how the sequence was built.
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
Use a parent pointer array (hash array) to reconstruct the actual elements of the LIS in O(N) time after populating the DP array.
Finding the length of the LIS is standard O(N²). But if you want to know *which* elements make up the sequence, you need to track how the sequence was built.
We use an array `hash` initialized to `hash[i] = i`. Whenever we extend a subsequence (`dp[i] = dp[j] + 1`), we set `hash[i] = j`.
We find the index in the `dp` array that has the maximum value. This is the end of our Longest Increasing Subsequence.
We jump backwards: `curr = hash[curr]`, adding elements to our result array. Since we start at the end, the result is backwards, so we reverse it before returning.