Skip to content

Instantly share code, notes, and snippets.

@loretoparisi
Created January 26, 2023 16:42
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save loretoparisi/2300c9b1d69110a9533bc396ef74b03b to your computer and use it in GitHub Desktop.
Save loretoparisi/2300c9b1d69110a9533bc396ef74b03b to your computer and use it in GitHub Desktop.
Longest Common Sub Sequence (LCS) Linear
def longest_subsequence_linear(seq, keyfn=lambda value: value):
''' Longest Increasing Subsequence
>>> seq = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
>>> lis(seq)
[0, 2, 6, 9, 11, 15]
>>> lis([])
[]
'''
if not seq: return seq
# tail[k] stores the position i of the smallest value seq[i] such that
# there is an increasing subsequence of length (k+1) ending at seq[i]
tail = []
# prev[k] stores the position i of the rightmost seq[i] such that
# seq[i] < seq[k]
prev = []
for i in range(len(seq)):
# find the rightmost tail[k] such that seq[tail[k]] < seq[i]
# TODO: bisect tail instead of linear scan
for k in range(len(tail)-1, -1, -1):
if keyfn(seq[tail[k]]) < keyfn(seq[i]):
if len(tail) == k+1:
tail.append(i)
elif keyfn(seq[tail[k+1]]) > keyfn(seq[i]):
tail[k+1] = i
prev.append(tail[k])
break
else:
tail.append(i)
prev.append(None)
i = tail[-1]
subseq = [seq[i]]
while prev[i] is not None:
i = prev[i]
subseq.append(seq[i])
subseq.reverse()
return subseq
@loretoparisi
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment