Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Longest Increasing Subsequence
Bookmark
Dynamic Programming
Binary Search
Input
Example 1
Example 2
Example 3
Custom
nums
=
[10, 9, 2, 5, 3, 7, 101, 18]
maxLength =
0
nums
10
9
2
5
3
7
101
18
dp
1
1
1
1
1
1
1
1
0
1
2
3
4
5
6
7
how long is the longest strictly increasing subsequence?
maxLength =
0
nums
10
9
2
5
3
7
101
18
dp
1
1
1
1
1
1
1
1
0
1
2
3
4
5
6
7
how long is the longest strictly increasing subsequence?
maxLength =
1
nums
10
9
2
5
3
7
101
18
dp
1
1
1
1
1
1
1
1
0
1
2
3
4
5
6
7
i = 2
j = 1
9
≥
2
: that chain cannot continue here
maxLength =
2
nums
10
9
2
5
3
7
101
18
dp
1
1
1
2
1
1
1
1
0
1
2
3
4
5
6
7
i = 3
dp[3] settled at
2
longest anywhere:
2
maxLength =
2
nums
10
9
2
5
3
7
101
18
dp
1
1
1
2
2
1
1
1
0
1
2
3
4
5
6
7
i = 4
dp[4] settled at
2
longest anywhere:
2
maxLength =
2
3
nums
10
9
2
5
3
7
101
18
dp
1
1
1
2
2
3
1
1
0
1
2
3
4
5
6
7
i = 5
j = 3
dp[5]
= dp[3] + 1 =
3
longest chain ending here
maxLength =
3
2
nums
10
9
2
5
3
7
101
18
dp
1
1
1
2
2
3
2
1
0
1
2
3
4
5
6
7
i = 6
j = 1
keep
dp[6] = 2
,
2
is not longer
maxLength =
3
3
nums
10
9
2
5
3
7
101
18
dp
1
1
1
2
2
3
3
1
0
1
2
3
4
5
6
7
i = 6
j = 4
keep
dp[6] = 3
,
3
is not longer
maxLength =
4
2
nums
10
9
2
5
3
7
101
18
dp
1
1
1
2
2
3
4
2
0
1
2
3
4
5
6
7
i = 7
j = 1
9
<
18
: extend, dp[1] + 1 =
2
vs dp[7] =
2
maxLength =
4
3
nums
10
9
2
5
3
7
101
18
dp
1
1
1
2
2
3
4
3
0
1
2
3
4
5
6
7
i = 7
j = 4
3
<
18
: extend, dp[4] + 1 =
3
vs dp[7] =
3
maxLength =
4
nums
10
9
2
5
3
7
101
18
dp
1
1
1
2
2
3
4
4
0
1
2
3
4
5
6
7
LIS:
2, 3, 7, 18
(length
4
)
algo
master
.
io
Step:
How long is the longest strictly increasing subsequence?
0 / 55
Input
Example 1
Example 2
Example 3
Custom
nums
=
[10, 9, 2, 5, 3, 7, 101, 18]
0 / 55
algo
master
.
io
Step:
How long is the longest strictly increasing subsequence?
