Kadanes Algorithmus erklärt

Question

Könnte mich jemand durchmachen, was hier in Kadanes Algorithmus vor sich geht? Wollte mein Verständnis überprüfen. Hier ist, wie ich es sehe.

Sie durchlaufen das Array und jedes Mal, wenn Sie die ans-Variable auf den größten Wert setzen, bis dieser Wert negativ wird, wird ans Null.

Gleichzeitig wird die Summenvariable jedes Mal durch die Schleife überschrieben, bis zum Maximum zwischen zuvor gesehenen Summen oder dem größten 'ans' bisher. Sobald die Schleife fertig ist, haben Sie die bisher größte Summe oder Antwort!

var sumArray = function(array) { 
     var ans = 0; 
     var sum = 0; 
     //loop through the array. 


     for (var i = 0; i < array.length; i++) { 
     //this is to make sure that the sum is not negative. 
     ans = Math.max(0, ans + array[i]); 

     //set the sum to be overwritten if something greater appears. 
     sum = Math.max(sum, ans) 
     } 

     return sum; 

    }; 

Answer 1

Betrachten Sie die Werte Tracing:

var maximumSubArray = function(array) { 
    var ans = 0; 
    var sum = 0; 

    console.log(ans, sum); 
    for (var i = 0; i < array.length; i++) { 

     ans = Math.max(0, ans + array[i]); 
     sum = Math.max(sum, ans); 
     console.log(ans, sum, array[i]); 
    } 
    console.log(ans, sum); 
    return sum; 

}; 

maximumSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]); 

Drucke:

0 0 
0 0 -2 
1 1 1 
0 1 -3 
4 4 4 
3 4 -1 
5 5 2 
6 6 1 
1 6 -5 
5 6 4 
5 6 

Die erste Spalte ist ans, die die Summe des aktuellen Sub-Array ist. Die zweite ist sum und repräsentiert die Summe der bisher größten. Das dritte ist das Element, das gerade besucht wurde. Sie können sehen, dass das zusammenhängende Subarray mit der größten Summe 4, −1, 2, 1 ist, mit Summe 6.

Das Beispiel ist von Wikipedia.

Das folgende ist eine Übersetzung des in Wikipedia unter dem Absatz angegebenen Codes: "Eine Variante des Problems, die das Zurückgeben von Subarrays der Länge Null nicht zulässt, für den Fall, dass das gesamte Array aus negativen Zahlen besteht mit dem folgenden Code gelöst werden:“

var maximumSubArray = function(array) { 
    var ans = array[0]; 
    var sum = array[0]; 

    console.log(ans, sum); 
    for (var i = 1; i < array.length; i++) { 

     ans = Math.max(ans, ans + array[i]); 
     sum = Math.max(sum, ans); 
     console.log(ans, sum, array[i]); 
    } 
    console.log(ans, sum); 
    return sum; 

}; 

sehen Sie, dass:

> maximumSubArray([-10, -11, -12]) 
-10 -10 
-10 -10 -11 
-10 -10 -12 
-10 -10 
-10 

die letzte Zahl ist das erwartete Ergebnis. Die anderen sind wie im vorherigen Beispiel.

Answer 2

Blick auf this link, gibt es eine klare Erklärung für Kadane-Algorithmus.

Grundsätzlich müssen Sie nach allen positiven zusammenhängenden Segmenten des Arrays suchen und auch das maximale zusammenhängende Segment bis zum Ende verfolgen. Immer wenn Sie ein neues positives zusammenhängendes Segment finden, überprüft es, ob die aktuelle Summe größer ist als max_sum und aktualisiert diese entsprechend.

Der folgende Code behandelt den Fall, wenn alle Zahlen negativ sind.

int maxSubArray(int a[], int size) 
{ 
    int max_so_far = a[0], i; 
    int curr_max = a[0]; 

    for (i = 1; i < size; i++) 
    { 
     curr_max = max(a[i], curr_max+a[i]); 
     max_so_far = max(max_so_far, curr_max); 
    } 
    return max_so_far; 
} 

Answer 3

würde ich eine funktionelle Art und Weise in JavaScript bevorzugen:

const maximumSubArray = function(array) { 
    return array.reduce(([acc, ans], x, i) => { 
    ans = Math.max(0, ans + x); 
    return [Math.max(acc, ans), ans]; 
    }, [array[0],array[0]])[0]; 
}; 

cl(maximumSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6 

Answer 4

Diese Pflegen beiden Situationen gemischt Array nehmen und all negative Zahl Array.

var maximumSubArray = function(arr) { 
 
    var max_cur=arr[0], max_global = arr[0]; 
 
    for (var i = 1; i < arr.length; i++) { 
 
     max_cur = Math.max(arr[i], max_cur + arr[i]); 
 
     max_global = Math.max(max_cur, max_global); 
 
    } 
 
    return max_global; 
 
}; 
 
console.log(maximumSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); 
 
console.log(maximumSubArray([-10, -11, -12]));

Answer 5

ich auch für alle negative Zahl in einem Array Kadane-Algorithmus enhacement getan haben.

int maximumSubSum(int[] array){ 
     int currMax =0; 
     int maxSum = 0; 

     //To handle All negative numbers 
     int max = array[0]; 
     boolean flag = true; 
     for (int i = 0; i < array.length; i++) { 

      //To handle All negative numbers to get at least one positive number 
      if(array[i]<0) 
       max= Math.max(max , array[i]); 
      else 
       flag = false; 


      currMax = Math.max(0, currMax + array[i]); 
      maxSum = Math.max(maxSum , currMax); 
     } 
     return flag?max:sum; 
    } 

Testfall: -30 -20 -10

-10

-10 -20 -30

-10

-2 -3 4 -1 -2 1 5 -3