Longest Increasing Subsequence: The 1D DP Double-Loop Pattern
Solve Longest Increasing Subsequence with bottom-up dynamic programming — the O(n²) double-loop dp array, a worked walkthrough, JavaScript code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Longest Increasing Subsequence is the problem that finally teaches most people what "optimal substructure" actually means. The prompt sounds innocent — find the longest run of numbers that keeps going up — but the numbers don't have to be next to each other, and that one word, subsequence, is what turns a five-second scan into a real dynamic-programming problem.
The trick is a reframe most beginners miss: instead of hunting for one global answer, you compute a small local answer at every index — how long is the best increasing subsequence that ends right here? — and let the big answer fall out of those.
Get this pattern and you own a whole family: the "look back at every earlier index and extend the best option" shape shows up across 1D DP.
The problem
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but is allowed to skip elements; "strictly increasing" means each chosen number is greater than the one before it, so equal values don't count.
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4 // the subsequence [2, 3, 7, 101] (or [2, 3, 7, 18]) has length 4Notice what you are not asked for: not the subsequence itself, just its length. And the winning numbers — 2, 3, 7, 101 — are scattered across the array with 9, 5, and others skipped between them. You cannot solve this by looking only at neighbors.
The brute force baseline
The definitional approach generates every subsequence and keeps the longest increasing one. For each element you either take it or skip it, which is 2ⁿ subsequences.
function lisBrute(nums, i = 0, prev = -Infinity) {
if (i === nums.length) return 0;
let skip = lisBrute(nums, i + 1, prev);
let take = 0;
if (nums[i] > prev) {
take = 1 + lisBrute(nums, i + 1, nums[i]);
}
return Math.max(skip, take);
}It's correct, but the take/skip tree branches at every index, giving O(2ⁿ) time. At n = 40 that's a trillion calls. The waste is that the same (i, prev) states get recomputed on thousands of different paths — which is exactly the signal that dynamic programming applies.
The key insight
Stop thinking about whole subsequences and think about endings.
Define dp[i] = the length of the longest strictly increasing subsequence that ends at index i (and must include nums[i]). Every element is a subsequence of length 1 by itself, so every dp[i] starts at 1.
Now the recurrence: a subsequence ending at i is just some shorter subsequence ending at an earlier index j, with nums[i] appended. That append is legal only when nums[j] < nums[i] (strictly increasing). So look back at every j < i, and whenever nums[j] < nums[i], you could extend that subsequence to length dp[j] + 1:
dp[i] = max(dp[i], dp[j] + 1) for every j < i where nums[j] < nums[i]Because you always build dp[i] from already-computed smaller answers to its left, each state is solved once. The final answer is the largest dp value anywhere — the best subsequence has to end somewhere, and dp tried every ending.
The optimal solution
This is the exact algorithm the visualizer traces: a dp array filled with 1s, an outer loop over each ending index i, and an inner loop scanning every earlier j to see which subsequences nums[i] can extend.
var lengthOfLIS = function (arr) {
let n = arr.length;
let dp = Array(n).fill(1);
dp[0] = 1;
let lisLength = 1;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
lisLength = Math.max(lisLength, dp[i]);
}
}
}
return lisLength;
};Two things worth calling out. First, lisLength tracks the running maximum as you go, so there's no separate final pass over dp. Second, it starts at 1: even a strictly decreasing array (where no nums[j] < nums[i] ever fires and the inner if never runs) correctly returns 1, because every single element is a valid length-1 subsequence.
Walkthrough
Trace nums = [3, 1, 8, 2, 5]. The dp array starts as [1, 1, 1, 1, 1] and lisLength = 1. Each row is one (i, j) comparison from the double loop.
| i | nums[i] | j | nums[j] | nums[j] < nums[i]? | dp after | lisLength |
|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 3 | no | [1,1,1,1,1] | 1 |
| 2 | 8 | 0 | 3 | yes → dp[2]=max(1,2)=2 | [1,1,2,1,1] | 2 |
| 2 | 8 | 1 | 1 | yes → dp[2]=max(2,2)=2 | [1,1,2,1,1] | 2 |
| 3 | 2 | 0 | 3 | no | [1,1,2,1,1] | 2 |
| 3 | 2 | 1 | 1 | yes → dp[3]=max(1,2)=2 | [1,1,2,2,1] | 2 |
| 3 | 2 | 2 | 8 | no | [1,1,2,2,1] | 2 |
| 4 | 5 | 0 | 3 | yes → dp[4]=max(1,2)=2 | [1,1,2,2,2] | 2 |
| 4 | 5 | 1 | 1 | yes → dp[4]=max(2,2)=2 | [1,1,2,2,2] | 2 |
| 4 | 5 | 2 | 8 | no | [1,1,2,2,2] | 2 |
| 4 | 5 | 3 | 2 | yes → dp[4]=max(2,3)=3 | [1,1,2,2,3] | 3 |
Final dp = [1, 1, 2, 2, 3], and lisLength = 3 — the subsequence [1, 2, 5]. Watch index 4: 5 first extends off 3 and 1 (both give length 2), but the winning move is extending off nums[3] = 2, whose own dp[3] is already 2, producing 2 + 1 = 3. That chaining — dp[4] built on dp[3] built on dp[1] — is optimal substructure doing its job.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (take/skip) | O(2ⁿ) | O(n) | branches at every index; recursion depth n |
| Bottom-up DP (double loop) | O(n²) | O(n) | inner loop scans all j < i for each of n indices |
| Patience sorting + binary search | O(n log n) | O(n) | binary-search each element into a "tails" array |
The DP version does roughly n²/2 comparisons — the outer loop runs n times and the inner loop grows from 1 up to n. The dp array is the only extra memory, so space is O(n). An O(n log n) variant exists (see the FAQ), but the O(n²) DP is the one to reach for first because it teaches the recurrence cleanly and extends to the "reconstruct the actual subsequence" follow-up.
Common mistakes
- Confusing subsequence with subarray. A subarray is contiguous; a subsequence can skip elements. In
[10, 9, 2, 5, 3, 7]the LIS is[2, 5, 7]even though those numbers aren't adjacent. If your loop only compares neighbors, you're solving the wrong problem. - Using
<=instead of<. "Strictly increasing" means equal values break the chain. In[2, 2, 2, 3]the answer is 2 ([2, 3]), not 4. The inner check must benums[j] < nums[i]. - Returning
dp[n-1]instead of the max. The best subsequence can end anywhere, not necessarily at the last index.[1, 2, 3, 0]has LIS 3 ending at index 2, whiledp[3]is only 1. TracklisLengthas a running max, or takeMath.max(...dp)at the end. - Forgetting the base case for empty input. An empty array has LIS 0; a single element has LIS 1. Initializing every
dp[i]to 1 handles the single-element and all-decreasing cases for free.
Where this pattern shows up next
The "initialize a dp cell, then look back and take the best extendable prior state" shape is the backbone of 1D dynamic programming:
- Min Cost Climbing Stairs — the same look-back recurrence, but each state picks the cheaper of the two prior steps.
- House Robber — a
dp[i] = max(skip, take)decision at every index, the linear cousin of the take/skip tree here. - House Robber II — House Robber wrapped into a circle, solved by running the 1D DP twice.
- Coin Change — the same "best over all valid predecessors" idea, but minimizing a count instead of maximizing a length.
You can also step through Longest Increasing Subsequence interactively to watch the dp array fill in and the extension arrows fire, one comparison at a time.
FAQ
What is the difference between a subsequence and a subarray?
A subarray is a contiguous slice — the elements must sit next to each other in the original array. A subsequence keeps the original order but is free to skip elements. That's why Longest Increasing Subsequence can pick 2, 3, 7, 101 out of [10, 9, 2, 5, 3, 7, 101, 18] while skipping everything in between. The skipping is exactly what makes it a DP problem instead of a simple linear scan.
Why does dp[i] represent subsequences ending at index i, not starting at it?
Anchoring dp[i] to a fixed ending lets you build each answer from already-computed answers to its left, in a single left-to-right pass. When you reach index i, every dp[j] for j < i is final, so extending is just dp[j] + 1. If dp[i] meant "best subsequence starting at i," you'd need future values that aren't computed yet, forcing a backward pass. The final answer is the maximum over all endings, since the best subsequence has to end somewhere.
What is the time complexity of the Longest Increasing Subsequence DP solution?
O(n²) time and O(n) space. The outer loop runs over each of the n ending indices, and for each one the inner loop scans every earlier index — about n²/2 comparisons total. The only extra memory is the dp array of length n. This is the standard interview-ready answer; a more advanced O(n log n) approach exists but is harder to reason about.
Can Longest Increasing Subsequence be solved faster than O(n²)?
Yes — there's an O(n log n) solution using "patience sorting." You maintain a tails array where tails[k] holds the smallest possible tail value of any increasing subsequence of length k + 1. For each number, binary-search for the leftmost tail that is >= it and overwrite that slot (or append if the number is larger than all tails). The length of tails at the end is the LIS length. It's faster, but it computes only the length cleanly; the O(n²) DP is easier to extend when you also need to reconstruct the actual subsequence.
How would I return the actual subsequence, not just its length?
Keep a parent array alongside dp. Whenever dp[i] improves by extending off index j, record parent[i] = j. Track the index where the global maximum dp value occurs, then walk the parent pointers backward from that index to the start, collecting values, and reverse them. That reconstruction is O(n) extra work on top of the O(n²) DP — one of the main reasons the DP formulation is worth learning even though the O(n log n) version is faster for length-only queries.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.