1. Empty input
No numbers means no subsequence.
if (nums.length === 0) return 0Typorithm · medium
Longest Increasing Subsequence
▷ Interactive algorithm lablongest-increasing-subsequence-dpdynamic-programmingsubsequencemaximization
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Longest Increasing Subsequence
Dynamic Programming
LIS DP stores the best increasing subsequence length ending at each index.
The state is anchored at an ending index.
Look back at earlier smaller values.
Extend the best compatible subsequence.
Preparing algorithm lab…
01
State: dp[i] is LIS ending at i.
02
Base: every element alone has length 1.
03
Transition: max(dp[j] + 1).
04
Answer: max over all endings.
function lengthOfLIS(nums) {
if (nums.length === 0) return 0;
const dp = Array(nums.length).fill(1);
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}Read the implementation
Connect each part of the code to the concept before you type.
2. Length one
Every number alone forms an increasing subsequence of length 1.
Array(nums.length).fill(1)3. Can extend
Only smaller previous values can come before nums[i].
if (nums[j] < nums[i])4. Extend best
Extend the best subsequence ending at j.
dp[i] = Math.max(dp[i], dp[j] + 1)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.