Gegeven is een rij getallen \(a_1,\ldots,a_n\). Een deelsequentie is een deelverzameling van deze reeks, genomen in de volgorde waarin ze in de sequentie voorkomen, van de vorm \(a_{i_1},a_{i_2},\ldots,a_{i_k}\) met \(1 \leq i_1 < i_2 < \ldots < i_k \leq n\). Een stijgende deelsequentie is een deelsequentie waarin de getallen strikt groter worden.

Gevraagd is de langst mogelijke stijgende deelsequentie in een gegevens rij te vinden.
Bijvoorbeeld, de langste stijgende deelsequentie van \((5,2,8,6,3,6,9,7)\) is \((2,3,6,9)\).

Ontwerp en implementeer een algoritme met dynamisch programmeren voor dit probleem.

Opgave

Schrijf een Python-functie vind_optimum(rij: list) die van een gegeven rij getallen de langst stijgende deelsequentie kan vinden.
Alle getallen in de rij zijn positieve gehele getallen. De functie moet zowel de getallen zelf teruggeven, als de indices waarop ze in de oorspronkelijke rij voorkomen.

Voorbeeld

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