find the largest increasing subsequence in an array
-
Hi,
Given an array with positive and negative integers, find the largest increasing subsequence in an array.
How can i implement it iterativly? does it have the same performance as when implemented it with dynamic programming?
-
Was willst du hier mit dynamischer Programmierung?
Du läufst einfach 1x über das Array drüber.
Dabei merkst du dir:
* longestStart = Anfang der längsten bisher gefundenen Sequenz
* longestLength = Länge der längsten bisher gefundenen Sequenz
* lastStart = Anfang der Sequenz die das letzte Element enthältVor der Schleife setzt du
longestStart = 0
longestLength = 1
lastStart = 0Die Schleife fängt bei Index 1 an (=das 2. Element).
Bei jedem Element guckst du ob es kleiner oder gleich dem vorigen Element ist.
Wenn ja, dann fängt hier eine neue Sequenz an.
In dem Fall berechnest du die Länge der Sequenz die das vorige Element enthältlastLength = currentIndex - lastStart.
Und wennlastLength > longestLength... naja, sollte klar sein.
Und natürlich nicht vergessen dass nach der Schleife nochmal gecheckt werden muss ob die Sequenz die das letzte Element enthält nicht vielleicht die längste war.D.h. du läufst 1x über das Array. Weniger geht nicht. Daher kann es auch keinen schnelleren Algorithmus geben (an der Komplexität gemessen, wobei ich auch nicht wüsste wie man hier noch irgendwelche linearen Optimierungen vornehmen sollte).
Einzig mit multithreading könnte man hier noch was reissen. Wäre aber deutlich aufwendiger als die oben beschriebene naive Implementierung.
-
muss die increasing subsequence zusammenhängend sein?
-
Oops.
/me hätte "subsequence" nachschlagen sollen, und nicht einfach annehmen dass die immer zusammenhängend sind...
-
