Challenge: LIS Reconstruction

The DP gives you the length, but which elements form the LIS? Track predecessors. When you update $dp[i] = dp[j] + 1$, record $prev[i] = j$.

This creates a chain of predecessors. Find the index with maximum $dp$ value. Follow $prev$ pointers backward, collecting elements. Reverse at the end. For $[10, 9, 2, 5, 3, 7, 101, 18]$: start at index $6$ (value $101$), follow back through $5, 3, 2$ to get $[2, 5, 7, 101]$.