Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Number of Longest Increasing Subsequence
Bookmark
Input
Example 1
Example 2 (all equal)
Example 3
Custom
nums
=
[1, 3, 5, 4, 7]
maxLen =
0
nums
1
3
5
4
7
len
1
1
1
1
1
cnt
1
1
1
1
1
0
1
2
3
4
not just how long, how MANY longest increasing subsequences?
maxLen =
0
nums
1
3
5
4
7
len
1
1
1
1
1
cnt
1
1
1
1
1
0
1
2
3
4
not just how long, how MANY longest increasing subsequences?
maxLen =
1
nums
1
3
5
4
7
len
1
1
1
1
1
cnt
1
1
1
1
1
0
1
2
3
4
i = 0
column 0 settled: len =
1
, cnt =
1
longest anywhere:
1
maxLen =
1
2
nums
1
3
5
4
7
len
1
2
1
1
1
cnt
1
1
1
1
1
0
1
2
3
4
i = 1
j = 0
1
<
3
, new best: len[1] =
2
, cnt[1] = cnt[0] =
1
maxLen =
2
2
nums
1
3
5
4
7
len
1
2
2
1
1
cnt
1
1
1
1
1
0
1
2
3
4
i = 2
j = 0
1
<
5
, new best: len[2] =
2
, cnt[2] = cnt[0] =
1
maxLen =
3
nums
1
3
5
4
7
len
1
2
3
1
1
cnt
1
1
1
1
1
0
1
2
3
4
i = 2
column 2 settled: len =
3
, cnt =
1
longest anywhere:
3
maxLen =
3
3
nums
1
3
5
4
7
len
1
2
3
3
1
cnt
1
1
1
1
1
0
1
2
3
4
i = 3
j = 1
3
<
4
, new best: len[3] =
3
, cnt[3] = cnt[1] =
1
maxLen =
3
nums
1
3
5
4
7
len
1
2
3
3
1
cnt
1
1
1
1
1
0
1
2
3
4
i = 3
column 3 settled: len =
3
, cnt =
1
longest anywhere:
3
maxLen =
3
3
nums
1
3
5
4
7
len
1
2
3
3
3
cnt
1
1
1
1
1
0
1
2
3
4
i = 4
j = 1
3
<
7
, new best: len[4] =
3
, cnt[4] = cnt[1] =
1
maxLen =
3
+1
nums
1
3
5
4
7
len
1
2
3
3
4
cnt
1
1
1
1
2
0
1
2
3
4
i = 4
j = 3
tie at length
4
: cnt[4] += cnt[3] =
1
→
2
maxLen =
4
result =
2
nums
1
3
5
4
7
len
1
2
3
3
4
cnt
1
1
1
1
2
0
1
2
3
4
2
longest subsequences (length
4
)
algo
master
.
io
Step:
How MANY longest increasing subsequences are there?
0 / 23
Input
Example 1
Example 2 (all equal)
Example 3
Custom
nums
=
[1, 3, 5, 4, 7]
0 / 23
algo
master
.
io
Step:
How MANY longest increasing subsequences are there?
