Longest Increasing Subsequence

Find the longest run of values that increases left to right, not necessarily adjacent. The O(n²) table is shown here because it is the version you can actually see working.

time O(n²) shown, O(n log n) possible

space O(n)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

dp[i] = length of the longest increasing subsequence ending at i
for i in 0..n-1:
  dp[i] = 1
  for j in 0..i-1:
    if a[j] < a[i]:
      dp[i] = max(dp[i], dp[j] + 1)
answer = max(dp)