(nontrivial) Increasing Subsequences
8
9
3
4
6
A[1]
A[2]
A[3]
A[4]
A[5]
8
9
3
9
3
4
(nontrivial) Increasing Subsequences
8
9
3
4
6
A[1]
A[2]
A[3]
A[4]
A[5]
3
4
6
4
6
3
6
Longest Increasing Subsequence
8
9
3
4
6
A[1]
A[2]
A[3]
A[4]
A[5]
1
LIS
Base case
Longest Increasing Subsequence
8
9
3
4
6
A[1]
A[2]
A[3]
A[4]
A[5]
1
LIS
2
Longest Increasing Subsequence
8
9
3
4
6
A[1]
A[2]
A[3]
A[4]
A[5]
1
LIS
2
1
Base case
Longest Increasing Subsequence
8
9
3
4
6
A[1]
A[2]
A[3]
A[4]
A[5]
1
LIS
2
1
3
Longest Increasing Subsequence
8
9
3
4
6
A[1]
A[2]
A[3]
A[4]
A[5]
1
LIS
2
1
3
2
LIS as Longest Path in a Graph
8
9
3
4
6
Longest Path in a Directed Acyclic Graph
8
9
3
4
6
State: longest[u], max length of path ending at uTransition: longest[u]=maxv-->ulongest[v] + length(v --> u)
Longest Path in a Directed Acyclic Graph
8
9
3
4
6
Longest[u]
0
Longest Path in a Directed Acyclic Graph
8
9
3
4
6
Longest[u]
0
0
Longest Path in a Directed Acyclic Graph
8
9
3
4
6
Longest[u]
1
0
0
Longest Path in a Directed Acyclic Graph
8
9
3
4
6
Longest[u]
1
1
0
0
Longest Path in a Directed Acyclic Graph
8
9
3
4
6
2
Longest[u]
1
1
0
0
Choose green edge because 1 > 0
Comment cards
https://goo.gl/RKd8vq
Test1
Reviewsession:5-7pm Tuesday Sep 19 inES&TRoomL1205.
Review notes, instructions page posted on course website
0
Embed
Upload