31 lines
660 B
Text
31 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)))
|