Maximale Teilfolge (Teilsumme ...) |
| 30.01.2008, 12:55 | Auf diesen Beitrag antworten » |
| JROppenheimer | 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 ... |
|
|
|
| 30.01.2008, 15:00 | Auf diesen Beitrag antworten » |
| Tobias | 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, 23:18 | Auf diesen Beitrag antworten » |
| JROppenheimer | 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. 
|
| 31.01.2008, 10:39 | Auf diesen Beitrag antworten » |
| JROppenheimer | 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! |
| Anzeige | |
|
|
|
| 31.01.2008, 22:42 | Auf diesen Beitrag antworten » |
| JROppenheimer | 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! |
|
|
