Algorytm kadane w java

Question

Mam następujące wdrożenie algorytmu Kadane w java. Chodzi o to, aby znaleźć maksymalną sumę sąsiednich podprzestrzeni.

String[] numbers = string.split(","); 
       int max_so_far = 0; 
       int max_ending_here = 0; 
       for (int i = 0; i < numbers.length-1;i++){ 
        max_ending_here = max_ending_here + Integer.parseInt(numbers[i]); 
        if (max_ending_here < 0) 
         max_ending_here = 0; 
        if (max_so_far < max_ending_here) 
          max_so_far = max_ending_here; 
       } 
       System.out.println(max_so_far); 

Jednak to nie działa, jeżeli nie jest połączenie kilku pozytywnych i negatywnych z tablicy, na przykład, następujące:

2,3,-2,-1,10 

, które należy zwrócić 12 jako maksimum. W tej chwili zwraca 5

Answer 1

Wdrożenie algorytmu wygląda dobrze, ale pętla warunkowa pętli i < numbers.length-1 nie: zatrzymuje się o 1 krótki koniec tablicy. i < numbers.length powinien to zrobić :-)

Answer 2

działa to dla mnie:

String string = "2,3,-2,-1,10"; 
    String[] numbers = string.split(","); 
    int max_so_far = 0; 
    int max_ending_here = 0; 
    for (String num : numbers) { 
     int x = Integer.parseInt(num); 
     max_ending_here = Math.max(0, max_ending_here + x); 
     max_so_far = Math.max(max_so_far, max_ending_here); 
    } 
    System.out.println(max_so_far); 

Answer 3

Odnośnie powyższego odpowiedź Michała Šrajer:

Linia nr 7: max_ending_here = Math.max (0, max_ending_here + x);

należy:

max_ending_here = Math.max (x, max_ending_here + x);

... zgodnie z algorytmem Kadaně zdefiniowanego here

Answer 4

zbyt późno, ale jeśli ktoś potrzebuje go w przyszłości.

public static void kadaneAlgo(int[][] array) 
    for(int i = 1; i < array.length; i++){ 
      int max_value_index_i = numberOrSum(array[i], past); 
      if(max_value_index_i > sum){ 
       sum = max_value_index_i; 
      } 
      past = max_value_index_i; 

     } 
     System.out.println("Max sum from a contiguous sub array is : " + sum); 
    } 

    public static int numberOrSum(int number, int past){ 
     return Math.max(number, number+past); 
    }