Given is a list of numbers \(a_1,\ldots,a_n\). A subsequence is a subset of this list, where the order of the elements remains unchanged. In other words, a list \(a_{i_1},a_{i_2},\ldots,a_{i_k}\) where \(1 \leq i_1 < i_2 < \ldots < i_k \leq n\). An increasing subsequence is a subesquence where every element is larger than the previous one.

Find the longest possible increasing subsequence in a given row. For example, the longest increasing subsequence of \((5,2,8,6,3,6,9,7)\) is \((2,3,6,9)\).

Design and implement an algorithm to solve this problem, using dynamic programming.

Assignment

Write a Python function find_optimum(numbers: list) that takes a list of numbers as argument and return the longest increasing subsequence. All numbers of this list are positive numbers. The function has to return both the numbers themself, as the indices where they appear in the original list.

Example

>>> find_optimum[5, 2, 8, 6, 3, 6, 9, 7])
([2, 3, 6, 7], [1, 4, 5, 7])
>>> find_optimum([7, 7, 1, 5])
([1, 5], [2, 3])
>>> find_optimum([6, 10, 4, 9, 3, 5])
([3, 5], [4, 5])
>>> find_optimum([3, 2, 10, 5, 9, 10, 3])
([2, 5, 9, 10], [1, 3, 4, 5])
>>> find_optimum([5, 2, 2, 6, 8, 9, 2, 6])
([2, 6, 8, 9], [2, 3, 4, 5])
>>> find_optimum([7, 6, 10, 4, 9, 8, 8, 9, 5])
([4, 8, 9], [3, 6, 7])
>>> find_optimum([1, 9, 1, 2, 7, 11, 11, 1, 10, 8])
([1, 2, 7, 8], [2, 3, 4, 9])
>>> find_optimum([6, 4, 6, 2, 4, 10, 4, 4, 3, 9, 8])
([2, 3, 8], [3, 8, 10])