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

- 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

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

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.

In [ ]:

```
class Subsequence(object):
def longest_inc_subseq(self, seq):
# TODO: Implement me
pass
```

**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()
```

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