Wie wird das maximale Sub-Array in Kadanes Algorithmus zurückgegeben?

8
%Vor%

Der obige Code gibt die Summe des maximalen Sub-Arrays zurück.

Wie würde ich stattdessen das Unterfeld zurückgeben, das die maximale Summe hat?

    
Aqib Saeed 15.10.2011, 13:48
quelle

5 Antworten

11

In etwa so:

%Vor%     
mikey 15.10.2011, 14:07
quelle
2

Der obige Code weist einen Fehler auf. Sollte sein:

%Vor%

NICHT:

%Vor%

Wenn nicht, würde eine Sequenz wie 2, 4, 22, 19, -48, -5, 20, 40 fehlschlagen und 55 anstelle der korrekten Antwort von 60 zurückgegeben.

SIEHE Kadane-Algorithmus bei Ссылка

    
Andy 19.06.2012 20:36
quelle
0

Ich verwalte das max_so_far in einer Liste:

%Vor%

Suchen Sie dann die größte Summe in der Liste, deren Index als Untersequenz endet. Beginnen Sie mit dem Index als Ende und suchen Sie rückwärts. Suchen Sie den letzten Index, dessen Wert positiv ist. Start der Untersequenz ist dieser Index.

%Vor%     
nathanlrf 04.01.2015 23:31
quelle
0

Ein einfacherer Ansatz, der eng mit dem Algorithmus verknüpft ist.

%Vor%

Sobald Sie den Start- und Endindex haben.

%Vor%     
Saras Arya 19.03.2015 13:05
quelle
0

Wir können das maximale Subarray mit folgendem Code verfolgen:

%Vor%

P.S. Angenommen, das angegebene Array ist ein Kandidat für das Max-Sub-Array-Problem und hat nicht alle negativen Elemente

    
optional 21.03.2017 02:33
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Temporäre Weiterleitung auf die Wartungsseite