algoritmo di kadane in java

Question

Ho la seguente implementazione dell'algoritmo di Kadane in java. È fondamentalmente trovare la somma massima di un sottarray contiguo.

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

Tuttavia questo non funziona se v'è una combinazione di un numero negativo e positivo in una matrice, per esempio i seguenti:

2,3,-2,-1,10 

che restituisce il 12 come massimo. A partire da ora restituisce 5

Answer 1

L'implementazione dell'algoritmo sembra ok, ma il ciclo condizionale i < numbers.length-1 non lo fa: si ferma a solo 1 breve della fine dell'array. i < numbers.length dovrebbe farlo :-)

Answer 2

questo funziona per me:

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

Per quanto riguarda la risposta di cui sopra da Michał Šrajer:

Linea # 7: max_ending_here = Math.max (0, max_ending_here + x);

dovrebbe essere:

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

... secondo l'algoritmo Kadane come definito here

Answer 4

troppo tardi, ma se qualcuno ha bisogno in futuro.

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