FAANGPrep Sprint

Longest Increasing Subsequence

Find how long the longest strictly increasing subsequence of the integer array nums is; its elements do not have to sit next to each other.

Medium

10 min

Solve on LeetCode

Examples

Input:nums = [10,9,2,5,3,7,101,18]

Output:4

Explain:

One longest run is [2,3,7,101]. It ends at index 6, so dp[7] is not the answer.

Input:nums = [0,1,0,3,2,3]

Output:4

Explain:

[0,1,2,3] is the longest strictly increasing subsequence.

Input:nums = [7,7,7,7,7]

Output:1

Explain:

Strictly increasing means equal values cannot extend each other.

Problem Understanding

A subsequence is derived by deleting some or no elements without changing the order.

Example: [10, 9, 2, 5, 3, 7, 101, 18]

One LIS: [2, 3, 7, 101]
Length: 4

Algorithm Strategy

dp[i] is the length of the longest strictly increasing subsequence that ends at index i.

Fixing the ending is what makes this decomposable: a run ending at i is some run ending at an earlier j with nums[j] < nums[i], plus nums[i] itself.

Recurrence: for every j < i with nums[j] < nums[i],

dp[i] = max(dp[i], dp[j] + 1)

Base case: every cell starts at 1 — a single element is already an increasing subsequence.

The answer is max(dp), not dp[n-1]. The longest run can end anywhere.

Interactive Visualization

dp[i] = THE LONGEST INCREASING RUN THAT ENDS AT i · OUTLINED = THE EARLIER INDEX BEING COMPARED

EVERY CELL STARTS AT 1

nums

101

comparing

—

longest so far

Answer

—

the rule

dp[i] = max(dp[i], dp[j] + 1)
for every j < i with nums[j] < nums[i]
answer = max(dp), not dp[n-1]

Every element is an increasing subsequence on its own, so every cell starts at 1

How long is the longest run ending at index 0, on 10?

nums

Legend & Complexity

dp[i] — the ending being decided

The earlier index j, in both rows

A dash: not computed yet

Time

O(n²)

Space

O(n)

With patience sorting

O(n log n)

Two rows: the value at each index, and the length of the longest run ending there. On every comparison the earlier index lights in both rows at once, so nums[j] < nums[i] and dp[j] + 1 read as one thing.

Watch the last frame: the answer cell is index 6, not index 7 — which is why the return is max(dp).

Dry Run

nums = [10, 9, 2, 5]

i	Val	Default	j (Comparing)	Extend?	New `dp[i]`
0	10	1	-	-	1
1	9	1	j=0 (10)	No (9<10)	1
2	2	1	j=0, j=1	No	1
3	5	1	j=2 (2)	Yes (5>2)	`dp[2]+1` = 2

Edge Cases & Common Mistakes

Details matter:

Strictly increasing. The test is nums[j] < nums[i], not <=. On [7,7,7,7,7] nothing extends anything and the answer is 1.
Return max(dp), not dp[n-1]. The longest run can end anywhere. This is the single most common wrong answer to this problem.
Every cell starts at 1, not 0. A single element is already an increasing subsequence of length 1, and a table of zeros would report 0 for an array that has one.

Solution

Every ending, against every earlier one — the lines light up as the figure above steps.

Longest Increasing Subsequence Code

1var lengthOfLIS = function(nums) {
2    const n = nums.length;
3    const dp = new Array(n).fill(1);
4    for (let i = 0; i < n; i++) {
5        for (let j = 0; j < i; j++) {
6            if (nums[j] < nums[i]) {
7                dp[i] = Math.max(dp[i], dp[j] + 1);
8            }
9        }
10    }
11    return Math.max(...dp);
12};