This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Solution Notebook¶

Constraints¶

• Are duplicates possible?
• Yes
• Can we assume the inputs are integers?
• Yes
• Can we assume the inputs are valid?
• No
• Do we expect the result to be an array of the longest increasing subsequence?
• Yes
• Can we assume this fits memory?
• Yes

Test Cases¶

• None -> Exception
• [] -> []
• [3, 4, -1, 0, 6, 2, 3] -> [-1, 0, 2, 3]

Algorithm¶

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:

• Time: O(n^2)
• Space: O(n)

Code¶

In [1]:
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]


Unit Test¶

In [2]:
%%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

In [3]:
%run -i test_longest_increasing_subseq.py

Success: test_longest_increasing_subseq