$./lis
# algorithm
1LIS(arr)
2begin
3 dp[i] ← 1 ∀i // each element is LIS of 1
4 for i ← 1 to n-1 do
5 for j ← 0 to i-1 do
6 if arr[j] < arr[i] and dp[j]+1 > dp[i]
7 dp[i] ← dp[j] + 1
8 parent[i] ← j
9 return max(dp), backtrack
10end
# array visualization
10
0
22
1
9
2
33
3
21
4
50
5
41
6
60
7
80
8
i (current) j (compare) LIS
# dp array
01
11
21
31
41
51
61
71
81
# variables
i-
j-
bestLength1
bestIdx0
# current action
click "run" to begin...