Die größte ansteigende Untersequenz hinter O(n*log(n))
Problem
Die numerische Sequenz wird durch die rekurrente Formel angegeben: ai+1=(k* ai+b)mod m. Finde die Länge der größten ansteigenden Teilsequenz.
Eingabe
Das Programm erhält fünf ganze Zahlen zum Eingang: die Länge der Sequenz n (1≤n≤105), das Startelement der Sequenz a1, die Parameter k, b, m, um die nachfolgenden Elemente der Sequenz zu berechnen (1≤m≤104, 0≤k<m, 0≤b<m, 0≤a1<m).
Ausgabe
Sie möchten die Länge der größten inkrementellen Untersequenz dieser Sequenz anzeigen.
|
Eingabe |
Ausgabe |
|
5 41 2 1 100 |
3 |