Algorytm Kadane'a wyjaśnił:

Question

Czy ktoś mógłby mnie przeprowadzić przez to, co dzieje się tutaj w algorytmie Kadane? Chciałem sprawdzić moje zrozumienie. Oto jak to widzę.

przechodzisz przez tablicę i za każdym razem, gdy ustawiasz zmienną ans na największą widzianą wartość, aż ta wartość stanie się ujemna, wtedy ans zmieni się na zero.

W tym samym czasie zmienna sumy jest nadpisywana za każdym razem w pętli, do maksimum między poprzednio widziane sumy lub największych "ans" do tej pory. Gdy pętla zostanie zakończona, będziesz mieć największą sumę lub odpowiedź widzianą do tej pory!

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

Rozważmy śledzenie wartości:

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]); 

Drukuje:

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 

pierwszej kolumnie jest ans, która jest sumą aktualnej subarray. Druga to sum, reprezentująca sumę największych dotychczas zaobserwowanych. Trzeci to właśnie odwiedzony element. Widać, że ciągła podrzędna o największej sumie to 4, −1, 2, 1, z sumą 6.

Przykład pochodzi z Wikipedia.

Poniżej znajduje się tłumaczenie kodu podanego w Wikipedii pod paragrafem: "Odmiana problemu, która nie pozwala na odjęcie podrozniesów o zerowej długości, w przypadku gdy cała tablica składa się z liczb ujemnych, może zostać rozwiązany za pomocą następującego kodu:”

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; 

}; 

Zobacz, że:

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

ostatni numer jest oczekiwany wynik. Pozostałe są takie, jak w poprzednim przykładzie.

Answer 2

spojrzenie na this link, daje jasne wyjaśnienie dla algorytmu Kadaně użytkownika.

Zasadniczo należy wyszukać wszystkie dodatnie, ciągłe segmenty tablicy, a także śledzić maksymalną sumę ciągłego segmentu do końca. Za każdym razem, gdy znajdziesz nowy dodatni ciągły segment, sprawdza on, czy aktualna suma jest większa niż dotychczas i odpowiednio aktualizuje.

Poniższy kod obsługuje przypadek, gdy wszystkie liczby są ujemne.

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

wolałbym sposób bardziej funkcjonalny w JavaScript:

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

To zajmie obu sytuacjach mieszany tablicy i wszystkie negatywne numer tablicy.

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

Zrobiłem enhacement algorytmu Kadaně dla wszystkich ujemnych liczby w tablicy, jak również.

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; 
    } 

testu obudowy: -30 -20 -10

-10

-10 -20 -30

-10

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