30 lines
660 B
Text
30 lines
660 B
Text
F longest_increasing_subsequence(x)
|
||
V n = x.len
|
||
V P = [0] * n
|
||
V M = [0] * (n + 1)
|
||
V l = 0
|
||
L(i) 0 .< n
|
||
V lo = 1
|
||
V hi = l
|
||
L lo <= hi
|
||
V mid = (lo + hi) I/ 2
|
||
I (x[M[mid]] < x[i])
|
||
lo = mid + 1
|
||
E
|
||
hi = mid - 1
|
||
V newl = lo
|
||
P[i] = M[newl - 1]
|
||
M[newl] = i
|
||
|
||
I (newl > l)
|
||
l = newl
|
||
|
||
[Int] s
|
||
V k = M[l]
|
||
L(i) (l - 1 .. 0).step(-1)
|
||
s.append(x[k])
|
||
k = P[k]
|
||
R reversed(s)
|
||
|
||
L(d) [[3, 2, 6, 4, 5, 1], [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]]
|
||
print(‘a L.I.S. of #. is #.’.format(d, longest_increasing_subsequence(d)))
|