Vibe Engines Learn
Algorithm · Dynamic Programming

The Longest Climb.

Don't memorize the longest increasing subsequence — watch it build. Pick elements left to right, keeping their order but skipping freely, to form the longest strictly rising run. The trick: the best run ending at an element is just one plus the best run ending on any earlier, smaller element. Fill that in for every position and the answer emerges — then trace the chain back.

subsequence · dp[i] = 1 + max(dp[j]) · O(n²)
SUBSEQUENCE

Keep order, skip freely — elements need not be adjacent.

dp[i]

Length of the longest increasing run that ends at index i.

EXTEND

dp[i] = 1 + the best dp[j] among earlier, smaller values.

ANSWER

The maximum over all dp[i]; trace back to rebuild the run.

lis.sim — array [3,1,4,1,5,9,2,6]
Ready

Top row is the array; bottom row is dp — the longest increasing run ending at each position. Press Step to fill dp left to right; each element extends the best earlier smaller one.

—
dp[i]
1
LIS length

Every ending, its longest run

Trying every subsequence is exponential. The DP insight is to anchor on where a subsequence ends: if you know, for every earlier position, the longest increasing run ending there, then the longest run ending at the current element is one more than the best of those earlier runs whose value is smaller. Compute that left to right and each element only looks back at the ones before it.

01

Start everyone at 1

Every element is an increasing run of length 1 on its own.

02

Look back for smaller

For element i, scan earlier elements j; if A[j] < A[i], you can extend that run.

03

Take the best

dp[i] = 1 + max(dp[j]) over those valid j — the longest run you can extend, plus this element.

04

Read and reconstruct

The largest dp value is the LIS length; follow the recorded predecessors back to list the subsequence.

Time (DP)
O(n²)
Faster
O(n log n)
Space
O(n)
Type
DP

The quadratic DP is the clearest way to see it, but LIS also has a slick O(n log n) solution called patience sorting: keep the smallest possible tail for a run of each length, and binary-search where each new element belongs. The length of that tails array is the LIS length. LIS underlies diff tools, longest-chain scheduling, and the box-stacking and Russian-doll problems.

SOLVE IT YOURSELF

Solve it: longest increasing subsequence

This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement lis_length(nums): return the length of the longest strictly increasing subsequence (keep order, drop elements freely). The classic dynamic program is O(n²): dp[i] = longest increasing run ending at i.

HINTS — 4 IDEAS
  1. Let dp[i] be the length of the longest increasing subsequence that ends at index i. Every element alone is length 1.
  2. For each i, look back at every j < i: if nums[j] < nums[i], you can extend that run — dp[i] = max(dp[i], dp[j] + 1).
  3. The answer is the largest value in dp.
  4. An empty array has length 0. (A faster O(n log n) patience-sorting version exists, but O(n²) is the clean starting point.)
CPython · WebAssembly

Check yourself

1 · What is dp[i] in the LIS dynamic program?

Each dp cell is the best increasing run that finishes exactly at that position.

2 · How is dp[i] computed?

Extend the best earlier run that ends on a smaller value; if none, dp[i] stays 1.

3 · What is the fast LIS complexity, and how?

Maintaining tails of each run length and binary-searching each element gives O(n log n).

Questions

Subsequence vs substring?

A substring is contiguous; a subsequence keeps order but may skip elements. LIS is about subsequences, so 3, 4, 5, 9 counts even though those values are not next to each other in the array.

Strictly vs non-decreasing?

Strictly increasing forbids equal neighbors (use A[j] < A[i]); the longest non-decreasing variant allows equals (A[j] ≤ A[i]). Same algorithm, one comparison changed.

How does patience sorting give the length?

Deal cards into piles where each card goes on the leftmost pile whose top is greater or equal (a binary search); the number of piles equals the LIS length. It is the same idea as the tails array in the O(n log n) method.

Anchor on the ending, extend the best.

Each element adds one to the longest smaller run before it. The max is your longest climb.

← All algorithms Edit Distance (DP) → Coin Change → Big-O Cheatsheet →
Finished this one? 0 / 47 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →