Given an array of numbers, longestIncreasingSubsequence(nums) returns the length of the longest subsequence whose values strictly increase from left to right. A subsequence keeps the original order but is allowed to skip elements — you can drop any numbers you like, but you cannot reorder the ones you keep. This shows up whenever you care about the longest run of "things only getting bigger" inside a fixed timeline: the longest stretch of months with rising revenue, the deepest chain of versions where each depends on an older one, the longest hand of cards you can play in increasing rank without rearranging the deck.
// nums: number[] — the input array (may be empty, may contain negatives or duplicates).
// returns: number — the LENGTH of the longest strictly increasing subsequence.
// Returns the length, NOT the subsequence itself.
function longestIncreasingSubsequence(nums: number[]): number;// Classic mixed case. One longest subsequence is [2, 5, 7, 101] (length 4).
// [2, 3, 7, 18] also works — there can be several, but the LENGTH is unique.
longestIncreasingSubsequence([10, 9, 2, 5, 3, 7, 101, 18]); // → 4// Strictly increasing means equal values DON'T extend the run.
longestIncreasingSubsequence([1, 2, 2, 3]); // → 3 ([1, 2, 3] — only one of the 2s counts)
longestIncreasingSubsequence([7, 7, 7, 7]); // → 1 (a single 7 is the best you can do)
longestIncreasingSubsequence([]); // → 0nums. [0, 1, 0, 3, 2, 3] has answer 4 via [0, 1, 2, 3], even though those values are scattered.nums first changes the answer — don't.0; a one-element array is 1. Every single element is trivially an increasing subsequence of length 1.You'll find the length of the longest run of strictly increasing values you can pull out of an array without reordering anything, by building up the answer one position at a time.
You have a row of numbers in a fixed order. You're allowed to cross some out, but you cannot move any — and you want the longest leftover run where each number is strictly bigger than the one before it. Picture a year of monthly revenue: [10, 9, 2, 5, 3, 7, 101, 18]. Some months dip. You want the longest stretch of months — not necessarily back-to-back — where revenue keeps climbing. Here one such stretch is 2 → 5 → 7 → 101, four months long, so the answer is 4. We return the length of that run, not the run itself.
The whole trick is to stop thinking about "the longest run anywhere" and instead ask a smaller, repeatable question: for each position i, what is the longest increasing run that ENDS exactly at nums[i]? Call that number dp[i].
Why end-anchored? Because a run that ends at i is built by gluing nums[i] onto the end of some shorter run that ended earlier — at a position j < i whose value is smaller than nums[i]. So dp[i] only depends on the dp values to its left. If you already know every dp[j] for j < i, computing dp[i] is just "look back, pick the best run I can extend, add one for myself."
Once every dp[i] is filled, the answer is the largest value in dp — because the longest run has to end somewhere, and dp has measured the best run ending at each possible spot.
Before the dynamic-programming insight, the obvious idea is brute force: every subsequence is defined by which elements you keep, so generate them all, throw away the ones that aren't strictly increasing, and report the longest.
function lisBruteForce(nums) {
let best = 0;
// Each of the 2^n subsets is encoded by the bits of `mask`.
for (let mask = 0; mask < 2 ** nums.length; mask++) {
const picked = [];
for (let i = 0; i < nums.length; i++) {
if (mask & (1 << i)) picked.push(nums[i]); // bit i set → keep nums[i]
}
// Is `picked` strictly increasing?
let ok = true;
for (let i = 1; i < picked.length; i++) {
if (picked[i] <= picked[i - 1]) { ok = false; break; }
}
if (ok) best = Math.max(best, picked.length);
}
return best;
}This is correct — it literally checks every possible subsequence — but it enumerates all 2^n subsets. At n = 40 that's over a trillion iterations; the function is unusable past ~25 elements. The waste is enormous: it rebuilds and re-checks runs from scratch that overlap heavily with runs it already examined. We never reuse the work of deciding "the best increasing run ending at index 5 has length 3." That reuse is exactly what dynamic programming buys us.
function longestIncreasingSubsequence(nums) {
const n = nums.length;
if (n === 0) return 0; // no elements → no subsequence
// dp[i] = length of the longest strictly increasing run that ENDS at i.
// Every element is a run of length 1 on its own, so start them all at 1.
const dp = new Array(n).fill(1);
let best = 1; // with n >= 1, the answer is at least 1
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
// Can nums[i] extend a run that ended at j? Only if it's STRICTLY larger.
if (nums[j] < nums[i]) {
// Best run ending at j, plus nums[i] itself.
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
best = Math.max(best, dp[i]); // the answer can end at any index
}
return best;
}
module.exports = { longestIncreasingSubsequence };The shift from the brute force is that we no longer build subsequences at all — we build a single array of answers to subproblems. Each dp[i] is computed once and then read by later positions instead of being recomputed. The outer loop walks i left to right so that by the time we reach i, every dp[j] it needs is already final. Here is the why behind the non-obvious lines:
dp.fill(1). Every element is, by itself, an increasing subsequence of length 1. Starting at 1 (not 0) bakes in "nums[i] alone" as the floor, so a position with no smaller element to its left correctly keeps dp[i] = 1.nums[j] < nums[i], strictly. This single < (not <=) is what makes the subsequence strictly increasing. With <=, equal values would chain and [7, 7, 7] would wrongly report 3.Math.max(dp[i], dp[j] + 1). There can be several earlier j we could extend; we want the longest one, so we keep the running max rather than the first or last match.best as we go. The longest run can end at any index — sometimes in the middle of the array, not at the end. We take the max over all dp[i] rather than returning dp[n - 1].Let's fill dp for the classic nums = [10, 9, 2, 5, 3, 7, 101, 18]. Every cell starts at 1.
i=0 nums[0]=10 no j to the left dp = [1, _, _, _, _, _, _, _]
i=1 nums[1]=9 j=0: 10<9? no dp[1] stays 1
i=2 nums[2]=2 j=0,1: 10<2? 9<2? no dp[2] stays 1
i=3 nums[3]=5 j=2: 2<5 -> dp[3]=dp[2]+1 dp[3]=2 (extends "2")
j=0,1: 10,9 not < 5
i=4 nums[4]=3 j=2: 2<3 -> dp[4]=dp[2]+1 dp[4]=2 (extends "2")
j=3: 5<3? no
i=5 nums[5]=7 j=2: 2<7 -> 1+1=2 dp[5] climbs to 3
j=3: 5<7 -> dp[3]+1=3 (extends "2,5")
j=4: 3<7 -> dp[4]+1=3 (or "2,3"); max keeps 3
i=6 nums[6]=101 j=5: 7<101 -> dp[5]+1=4 dp[6]=4 (extends "2,5,7")
i=7 nums[7]=18 j=5: 7<18 -> dp[5]+1=4 dp[7]=4 (extends "2,5,7")
j=6: 101<18? no
dp = [1, 1, 1, 2, 2, 3, 4, 4] -> answer = max(dp) = 4
The interesting position is i=5 (the value 7). Three earlier elements are smaller than 7 — the 2, the 5, and the 3 — so 7 could extend the run ending at any of them. We take the best: the runs ending at 5 and at 3 both have length 2, giving dp[5] = 3. Then 101 extends that to 4. The maximum cell, 4, is our answer.
nums[j] < nums[i]. If you write <=, equal values chain together and [2, 2, 2] reports 3 instead of 1. The spec asks for strictly increasing, so duplicates must never extend a run — that's exactly what the [7, 7, 7, 7] -> 1 test pins down.j loop deliberately ranges over all earlier indices, not just i - 1, so non-adjacent picks like [0, 1, 2, 3] out of [0, 1, 0, 3, 2, 3] are found. If you only compared each element to its immediate predecessor, you'd be solving "longest increasing subarray," a different and easier problem.dp to 1, not 0. Each element alone is a run of length 1. Starting at 0 makes a single-element array return 0 and breaks the all-decreasing case — every dp[i] would stay 0 and the answer would come out 0 instead of 1.j, not the first match. A later element may be able to extend several earlier runs; you want the longest, so dp[i] must be the maximum of dp[j] + 1 over every qualifying j. Grabbing the first j that satisfies nums[j] < nums[i] undercounts.dp[n - 1] instead of max(dp). The longest run frequently ends in the middle of the array. In [4, 10, 4, 3, 8, 9] the best run 4, 8, 9 happens to end at the last index, but in [1, 5, 2, 3] the longest run 1, 2, 3 ends one short of the end. Always scan the whole dp array for its maximum.n === 0 there is nothing to loop over and best should be 0, not 1. The early return 0 handles it; without that guard, initialising best = 1 would wrongly report 1 for [].dp, keep a prev[i] that records which j gave dp[i] its value (or -1 if nums[i] started its own run). After filling, find the index with the maximum dp, then walk prev backwards to read the elements off in reverse. This turns the length into one concrete witnessing subsequence at no extra asymptotic cost.tails where tails[k] is the smallest value that can end an increasing run of length k + 1. For each incoming number, binary-search for the first entry >= it and overwrite that slot, or append if the number is larger than everything. The length of tails at the end is the answer, and each step is a binary search, so the whole thing runs in O(n log n) — the standard speedup when n is large. Note that tails is not itself a valid subsequence; only its length is meaningful.count[i] tracking how many distinct longest runs end at i. When dp[j] + 1 beats dp[i], reset count[i] = count[j]; when it ties the current best, add count[j] to it. Summing count[i] over all i with the maximal dp[i] gives the number of distinct longest increasing subsequences — a common follow-up interview question.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Given an array of numbers, longestIncreasingSubsequence(nums) returns the length of the longest subsequence whose values strictly increase from left to right. A subsequence keeps the original order but is allowed to skip elements — you can drop any numbers you like, but you cannot reorder the ones you keep. This shows up whenever you care about the longest run of "things only getting bigger" inside a fixed timeline: the longest stretch of months with rising revenue, the deepest chain of versions where each depends on an older one, the longest hand of cards you can play in increasing rank without rearranging the deck.
// nums: number[] — the input array (may be empty, may contain negatives or duplicates).
// returns: number — the LENGTH of the longest strictly increasing subsequence.
// Returns the length, NOT the subsequence itself.
function longestIncreasingSubsequence(nums: number[]): number;// Classic mixed case. One longest subsequence is [2, 5, 7, 101] (length 4).
// [2, 3, 7, 18] also works — there can be several, but the LENGTH is unique.
longestIncreasingSubsequence([10, 9, 2, 5, 3, 7, 101, 18]); // → 4// Strictly increasing means equal values DON'T extend the run.
longestIncreasingSubsequence([1, 2, 2, 3]); // → 3 ([1, 2, 3] — only one of the 2s counts)
longestIncreasingSubsequence([7, 7, 7, 7]); // → 1 (a single 7 is the best you can do)
longestIncreasingSubsequence([]); // → 0nums. [0, 1, 0, 3, 2, 3] has answer 4 via [0, 1, 2, 3], even though those values are scattered.nums first changes the answer — don't.0; a one-element array is 1. Every single element is trivially an increasing subsequence of length 1.You'll find the length of the longest run of strictly increasing values you can pull out of an array without reordering anything, by building up the answer one position at a time.
You have a row of numbers in a fixed order. You're allowed to cross some out, but you cannot move any — and you want the longest leftover run where each number is strictly bigger than the one before it. Picture a year of monthly revenue: [10, 9, 2, 5, 3, 7, 101, 18]. Some months dip. You want the longest stretch of months — not necessarily back-to-back — where revenue keeps climbing. Here one such stretch is 2 → 5 → 7 → 101, four months long, so the answer is 4. We return the length of that run, not the run itself.
The whole trick is to stop thinking about "the longest run anywhere" and instead ask a smaller, repeatable question: for each position i, what is the longest increasing run that ENDS exactly at nums[i]? Call that number dp[i].
Why end-anchored? Because a run that ends at i is built by gluing nums[i] onto the end of some shorter run that ended earlier — at a position j < i whose value is smaller than nums[i]. So dp[i] only depends on the dp values to its left. If you already know every dp[j] for j < i, computing dp[i] is just "look back, pick the best run I can extend, add one for myself."
Once every dp[i] is filled, the answer is the largest value in dp — because the longest run has to end somewhere, and dp has measured the best run ending at each possible spot.
Before the dynamic-programming insight, the obvious idea is brute force: every subsequence is defined by which elements you keep, so generate them all, throw away the ones that aren't strictly increasing, and report the longest.
function lisBruteForce(nums) {
let best = 0;
// Each of the 2^n subsets is encoded by the bits of `mask`.
for (let mask = 0; mask < 2 ** nums.length; mask++) {
const picked = [];
for (let i = 0; i < nums.length; i++) {
if (mask & (1 << i)) picked.push(nums[i]); // bit i set → keep nums[i]
}
// Is `picked` strictly increasing?
let ok = true;
for (let i = 1; i < picked.length; i++) {
if (picked[i] <= picked[i - 1]) { ok = false; break; }
}
if (ok) best = Math.max(best, picked.length);
}
return best;
}This is correct — it literally checks every possible subsequence — but it enumerates all 2^n subsets. At n = 40 that's over a trillion iterations; the function is unusable past ~25 elements. The waste is enormous: it rebuilds and re-checks runs from scratch that overlap heavily with runs it already examined. We never reuse the work of deciding "the best increasing run ending at index 5 has length 3." That reuse is exactly what dynamic programming buys us.
function longestIncreasingSubsequence(nums) {
const n = nums.length;
if (n === 0) return 0; // no elements → no subsequence
// dp[i] = length of the longest strictly increasing run that ENDS at i.
// Every element is a run of length 1 on its own, so start them all at 1.
const dp = new Array(n).fill(1);
let best = 1; // with n >= 1, the answer is at least 1
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
// Can nums[i] extend a run that ended at j? Only if it's STRICTLY larger.
if (nums[j] < nums[i]) {
// Best run ending at j, plus nums[i] itself.
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
best = Math.max(best, dp[i]); // the answer can end at any index
}
return best;
}
module.exports = { longestIncreasingSubsequence };The shift from the brute force is that we no longer build subsequences at all — we build a single array of answers to subproblems. Each dp[i] is computed once and then read by later positions instead of being recomputed. The outer loop walks i left to right so that by the time we reach i, every dp[j] it needs is already final. Here is the why behind the non-obvious lines:
dp.fill(1). Every element is, by itself, an increasing subsequence of length 1. Starting at 1 (not 0) bakes in "nums[i] alone" as the floor, so a position with no smaller element to its left correctly keeps dp[i] = 1.nums[j] < nums[i], strictly. This single < (not <=) is what makes the subsequence strictly increasing. With <=, equal values would chain and [7, 7, 7] would wrongly report 3.Math.max(dp[i], dp[j] + 1). There can be several earlier j we could extend; we want the longest one, so we keep the running max rather than the first or last match.best as we go. The longest run can end at any index — sometimes in the middle of the array, not at the end. We take the max over all dp[i] rather than returning dp[n - 1].Let's fill dp for the classic nums = [10, 9, 2, 5, 3, 7, 101, 18]. Every cell starts at 1.
i=0 nums[0]=10 no j to the left dp = [1, _, _, _, _, _, _, _]
i=1 nums[1]=9 j=0: 10<9? no dp[1] stays 1
i=2 nums[2]=2 j=0,1: 10<2? 9<2? no dp[2] stays 1
i=3 nums[3]=5 j=2: 2<5 -> dp[3]=dp[2]+1 dp[3]=2 (extends "2")
j=0,1: 10,9 not < 5
i=4 nums[4]=3 j=2: 2<3 -> dp[4]=dp[2]+1 dp[4]=2 (extends "2")
j=3: 5<3? no
i=5 nums[5]=7 j=2: 2<7 -> 1+1=2 dp[5] climbs to 3
j=3: 5<7 -> dp[3]+1=3 (extends "2,5")
j=4: 3<7 -> dp[4]+1=3 (or "2,3"); max keeps 3
i=6 nums[6]=101 j=5: 7<101 -> dp[5]+1=4 dp[6]=4 (extends "2,5,7")
i=7 nums[7]=18 j=5: 7<18 -> dp[5]+1=4 dp[7]=4 (extends "2,5,7")
j=6: 101<18? no
dp = [1, 1, 1, 2, 2, 3, 4, 4] -> answer = max(dp) = 4
The interesting position is i=5 (the value 7). Three earlier elements are smaller than 7 — the 2, the 5, and the 3 — so 7 could extend the run ending at any of them. We take the best: the runs ending at 5 and at 3 both have length 2, giving dp[5] = 3. Then 101 extends that to 4. The maximum cell, 4, is our answer.
nums[j] < nums[i]. If you write <=, equal values chain together and [2, 2, 2] reports 3 instead of 1. The spec asks for strictly increasing, so duplicates must never extend a run — that's exactly what the [7, 7, 7, 7] -> 1 test pins down.j loop deliberately ranges over all earlier indices, not just i - 1, so non-adjacent picks like [0, 1, 2, 3] out of [0, 1, 0, 3, 2, 3] are found. If you only compared each element to its immediate predecessor, you'd be solving "longest increasing subarray," a different and easier problem.dp to 1, not 0. Each element alone is a run of length 1. Starting at 0 makes a single-element array return 0 and breaks the all-decreasing case — every dp[i] would stay 0 and the answer would come out 0 instead of 1.j, not the first match. A later element may be able to extend several earlier runs; you want the longest, so dp[i] must be the maximum of dp[j] + 1 over every qualifying j. Grabbing the first j that satisfies nums[j] < nums[i] undercounts.dp[n - 1] instead of max(dp). The longest run frequently ends in the middle of the array. In [4, 10, 4, 3, 8, 9] the best run 4, 8, 9 happens to end at the last index, but in [1, 5, 2, 3] the longest run 1, 2, 3 ends one short of the end. Always scan the whole dp array for its maximum.n === 0 there is nothing to loop over and best should be 0, not 1. The early return 0 handles it; without that guard, initialising best = 1 would wrongly report 1 for [].dp, keep a prev[i] that records which j gave dp[i] its value (or -1 if nums[i] started its own run). After filling, find the index with the maximum dp, then walk prev backwards to read the elements off in reverse. This turns the length into one concrete witnessing subsequence at no extra asymptotic cost.tails where tails[k] is the smallest value that can end an increasing run of length k + 1. For each incoming number, binary-search for the first entry >= it and overwrite that slot, or append if the number is larger than everything. The length of tails at the end is the answer, and each step is a binary search, so the whole thing runs in O(n log n) — the standard speedup when n is large. Note that tails is not itself a valid subsequence; only its length is meaningful.count[i] tracking how many distinct longest runs end at i. When dp[j] + 1 beats dp[i], reset count[i] = count[j]; when it ties the current best, add count[j] to it. Summing count[i] over all i with the maximal dp[i] gives the number of distinct longest increasing subsequences — a common follow-up interview question.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.