This notebook was prepared by Donne Martin. Source and license info is on GitHub.
We'll use bottom up dynamic programming to build a table.
Init a temp array of size len(input) to 1. We'll use l and r to iterate through the input. Array prev will hold the index of the prior smaller value, used to reconstruct the final sequence. if input[l] < input[r]: if temp[r] < temp[l] + 1: temp[r] = temp[l] + 1 prev[r] = l l r index: 0 1 2 3 4 5 6 --------------------------- input: 3 4 -1 0 6 2 3 temp: 1 2 1 1 1 1 1 prev: x x x x x x x End result: index: 0 1 2 3 4 5 6 --------------------------- input: 3 4 -1 0 6 2 3 temp: 1 2 1 2 3 3 4 prev: x 0 x 2 1 3 5
Complexity:
class Subsequence(object):
def longest_inc_subseq(self, seq):
if seq is None:
raise TypeError('seq cannot be None')
if not seq:
return []
temp = [1] * len(seq)
prev = [None] * len(seq)
for r in range(1, len(seq)):
for l in range(r):
if seq[l] < seq[r]:
if temp[r] < temp[l] + 1:
temp[r] = temp[l] + 1
prev[r] = l
max_val = 0
max_index = -1
results = []
for index, value in enumerate(temp):
if value > max_val:
max_val = value
max_index = index
curr_index = max_index
while curr_index is not None:
results.append(seq[curr_index])
curr_index = prev[curr_index]
return results[::-1]
%%writefile test_longest_increasing_subseq.py
import unittest
class TestLongestIncreasingSubseq(unittest.TestCase):
def test_longest_increasing_subseq(self):
subseq = Subsequence()
self.assertRaises(TypeError, subseq.longest_inc_subseq, None)
self.assertEqual(subseq.longest_inc_subseq([]), [])
seq = [3, 4, -1, 0, 6, 2, 3]
expected = [-1, 0, 2, 3]
self.assertEqual(subseq.longest_inc_subseq(seq), expected)
print('Success: test_longest_increasing_subseq')
def main():
test = TestLongestIncreasingSubseq()
test.test_longest_increasing_subseq()
if __name__ == '__main__':
main()
Overwriting test_longest_increasing_subseq.py
%run -i test_longest_increasing_subseq.py
Success: test_longest_increasing_subseq