algoritmo kadane en java

Question

Tengo la siguiente implementación del algoritmo de Kadane en java. Básicamente, es para encontrar la suma máxima de subcampos contiguos.

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

Sin embargo, esto no funciona si hay una combinación de un número negativo y positivo en una matriz, por ejemplo el siguiente:

2,3,-2,-1,10 

que debe devolver un 12 como máximo. A partir de ahora, devuelve 5

Answer 1

La implementación del algoritmo se ve bien, pero su condicional de condicional i < numbers.length-1 no: se detiene solo 1 corto del final de la matriz. i < numbers.length debe hacerlo :-)

Answer 2

esto funciona para mí:

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

En cuanto a la respuesta anterior de Michał Šrajer:

la línea # 7: max_ending_here = Math.max (0, x + max_ending_here);

debería ser:

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

... según el algoritmo kadane como se define here

Answer 4

demasiado tarde, pero si alguien lo necesita en el 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); 
    }