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

Challenge 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¶

Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.

Code¶

In [ ]:
class Subsequence(object):

def longest_inc_subseq(self, seq):
# TODO: Implement me
pass


Unit Test¶

The following unit test is expected to fail until you solve the challenge.

In [ ]:
# %load 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()


Solution Notebook¶

Review the Solution Notebook for a discussion on algorithms and code solutions.