"""LongestIncreasingSubsequence.py
Find longest increasing subsequence of an input sequence.
D. Eppstein, April 2004
"""
import unittest
from bisect import bisect_left
def LongestIncreasingSubsequence(S):
"""
Find and return longest increasing subsequence of S.
If multiple increasing subsequences exist, the one that ends
with the smallest value is preferred, and if multiple
occurrences of that value can end the sequence, then the
earliest occurrence is preferred.
"""
# The main data structures: head[i] is value x from S that
# terminates a length-i subsequence, and tail[i] is either
# None (if i=0) or the pair (head[i-1],tail[i-1]) as they
# existed when x was processed.
head = []
tail = [None]
for x in S:
i = bisect_left(head,x)
if i >= len(head):
head.append(x)
if i > 0:
tail.append((head[i-1],tail[i-1]))
elif head[i] > x:
head[i] = x
if i > 0:
tail[i] = head[i-1],tail[i-1]
if not head:
return []
output = [head[-1]]
pair = tail[-1]
while pair:
x,pair = pair
output.append(x)
output.reverse()
return output
# If run as "python LongestIncreasingSubsequence.py", run tests on various
# small lists and check that the correct subsequences are generated.
class LISTest(unittest.TestCase):
def testLIS(self):
self.assertEqual(LongestIncreasingSubsequence([]),[])
self.assertEqual(LongestIncreasingSubsequence(range(10,0,-1)),[1])
self.assertEqual(LongestIncreasingSubsequence(range(10)),
list(range(10)))
self.assertEqual(LongestIncreasingSubsequence([3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]),
[1,2,3,5,8,9])
if __name__ == "__main__":
unittest.main()