Gegeven is een rij getallen \(a_1,\ldots,a_n\). Een deelsequentie is een sequentie 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 stijgend zijn.

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

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

Implementeer de interface Subsequencer¹ in een klasse genaamd DynamicSubsequencer. Schrijf een methode List<Integer> findSubsequence(List<Integer> sequence) die de indices teruggeeft van een langste stijgende deelrij.

Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.