ā† Back

šŸ—¼ Rising Tower

Build the Longest Increasing Subsequence ā€¢ O(nĀ²) DP visualization

šŸ—¼ Tower Visualization

šŸ“Š DP Array (dp[i] = LIS ending at index i)

šŸ“ LIS DP O(nĀ²)

dp[i] = LIS length ending at i

for each j < i:
  if arr[j] < arr[i]:
    dp[i] = max(dp[i], dp[j]+1)

Answer = max(dp[i])
Array Size
-
Comparisons
0
LIS Length
?

šŸ’” Key Insight

For each element, look at ALL
previous smaller elements and
take the best LIS to extend.

There's also O(n log n) using
binary search + patience sorting!