 Maximale Teilfolge (Teilsumme ...) |
|
|
| Maximale Teilfolge (Teilsumme ...) |
     |
Ich sitz hier mal wieder an einem wohl etwas banalen Problem. Ichb in mir sicher, die Lösung ist in irgend nem Buch oder Skript, aber ich würde gern druaf kommen, indem ich nicht die "Komplettlösung" lese, sondern maximal Tips benutze ....
In einem Array A = [a1,.....,an] sind die Indize i,j gesucht, sodass die Summe über die Elemente von i bist j maximal ist. Dabei kann A auch negatige Elemente enthalten.
Das ganze soll per D&C in n log2 n gelöst werden.
Ich denke ich bin kurz vor lösung, aber mir fehlt sicher nur ein kniff.....
Es können 3 Fälle eintreten:
1. Maximale Teilfolge liegt in die linken hälfte von A
2. Maximale Teilfolge liegt in die rechtn hälfte von A
3. Maximale Teilfolge liegt sowohl in der linken als auch in der rechten hälfte von A (also über die "mitte" hinaus)
Das ganze n log2 n sagt mir ja schon, dass ich die Mengen halbieren muss, aber ich hab ein kleines Problem beim Abbruch.
Habe ich nur noch 2 Elemente von mir aus [a1,a2] stoße ich ja quasi auf den grund des problems. das maximum ist a1, oder a2 oder a1+a2, das wäre linear lösbar, aber jeh nach Fall, bin ihc mir nicht sicher wie ich weiter machen muss.
ist das maximum a1, dann geb ich die indize i=j=1 zurück
ist das maximum a2, dann geb ich die inize i=j=2 zurück
ist das maximum a1+a2 dann gieb ich i=1 und j=2 zurück
und dann hänge ich. WIE setze ich denn die lösungen aus [a1,a2] und [a3,a4] zusammen?! wenn ich das weiss, dann kann das ja rekursiv wiederholt werden bis ich die lösung fürs ganze habe ...
hat jemand einen Tip?
ich habe in einer teillaufgabe vorher herausgefunden, dass wenn ein k bekannt ist für das i>=k>=j gilt, dass ich das Problem dann linear in O(n) lösen kann, also dachte ich, ich kann das hier vlt anwenden.....jeh nach ergebnis, einfach das k ändern und dann mit dem k in linearer Zeit die maximale Summe finden?
Vlt. hier den Schritt hoch zu den 3 Fällen und dann vergleichen, bin aber bissie festgefahren gerade ...
__________________
I'm 71% Megatron!
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von JROppenheimer: 30.01.2008 12:56.
|
|
30.01.2008 12:55 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
 |
|
Na du sitzt doch mit der Nase schon vor der Lösung. 
Du hast also einen Algo in O(n), der dir sagt, wo i und j liegen, wenn du ein k kennst mit i>=k>=j. Wichtig ist also die Erkenntnis, dass das k-te Folgenglied ein Summand der zusammenhängenden Teilfolge ist.
Was du jetzt nach prüfen musst ist, ob es eine größere Summe gibt, in der das k-te Folgenglied NICHT vorkommt. Da die Summe aus zusammenhängenden Folgenglieder besteht, musst du also die Teilfolgen (a_1, ..., a_k-1) und (a_k+1, ..., a_n) untersuchen.
Verstehst du also das Vorgehen?
|
|
|
30.01.2008 15:00 |
|
|
|
|
Einfach das erste k auf 1/2 n setzen. dann kucken wo die i und j sind, damit die summe maximal ist.
dann mache ich das ganze und vergleich das ergibnis, wenn ich das array "teile" also in eins von 1 - k-1 und eins von k+1 bis n
da setze ich dann k "genau" in die mitte und mache das solange bis ich bei abbruch bin. Abbruch müsst sein, wenn die arrays nur noch ein element groß sind.
ich hoffe ich drück mich net total bekloppt aus, aber ich msus ehrlich sagen mir fehlt gerade die motivation das genauer zu formulieren.
im grunde ist es ähnlich wie quicksort. analog wäre k das pivot element, das die arrays teilt. 
__________________
I'm 71% Megatron!
|
|
|
30.01.2008 23:18 |
|
|
|
|
Ich bearbeite gerade ein ähnliches Problem.
Gegeben ist ein Array mit Werten und gesucht sind i,j, mit i<j sodass A[j]-A[i] maximal ist.
Das kann ich doch genau so lösen, oder?
Ich setze als erstes ein k = n/2. dann lasse ich zwei "Zeiger" laufen. Der erste von k bis 1 und der zweite von k+1 bis n. Dann erhalte ich das größte Elemente "rechts" und das kleinste Element "links" von k.
Problem: Es könnte auch sein, dass sich beide Indize "rechts" oder "links" von k im Array befinden. Als muss ich rekursiv das Array immer schön halbieren und das Spiel ähnlich wie bei dem Problem vorher rekursiv auf die Teilarrays anwenden, bis das Problem klein genug ist. Das wäre dann, wenn das Teilarray nur noch 2 Elemente hat, oder?
Bin aber nicht ganz sicher, ob das so stimmt. ...
Rekursionen machen mir ein wenig n knoten in den kopp!
__________________
I'm 71% Megatron!
|
|
|
31.01.2008 10:39 |
|
|
|
|
ich könnte kotzen....nach stunden um stunden vor dem problem ist mir isn auge gesprungen wo mein fehler war ....
ich habs hinbekommen, danke für die tips!
__________________
I'm 71% Megatron!
|
|
|
31.01.2008 22:42 |
|
|
|
