kadane algoritmo números negativos

Question

int array[] = {-1, 4, -2, 5, -5, 2, -20, 6}; 

Si tuviera esa matriz, mi implementación del algoritmo kadane para encontrar el máximo subarreglo funciona:

int max_so_far = INT_MIN; 
    int max_ending_here = 0; 
    for (int i = 0; i < size; i++) { 
    max_ending_here = max(max_ending_here + array[i], 0); 
    max_so_far = max(max_ending_here, max_so_far); 
    } 

    printf("%d\n", max_so_far); 

Sin embargo, si tengo una matriz de todos los negativos:

int array[]= {-10, -10, -10}; 

No funcionará, debería devolver -10, pero obtengo 0.

¿Cómo puedo hacer que funcione también para números negativos?

¡Gracias!

Answer 1

De acuerdo con Wikipedia, el algoritmo de Kadane requiere al menos un número positivo, por lo que su matriz negativa es una entrada no válida.

Answer 2

Cuando todos los elementos son negativos, el subconjunto máximo es el subconjunto vacío, que tiene suma 0.

Pero si desea cambiar el algoritmo para almacenar el elemento más grande en este caso, podría hacer lo siguiente:

int max_so_far  = INT_MIN; 
int max_ending_here = 0; 
int max_element  = INT_MIN; 

for (int i = 0; i < size; i++) 
{ 
    max_ending_here = max(max_ending_here + array[i], 0); 
    max_so_far  = max(max_ending_here, max_so_far); 
    max_element  = max(max_element, array[i]); 
} 

if (max_so_far == 0) 
    max_so_far = max_element; 

printf("%d\n", max_so_far); 

Answer 3

Si todos los elementos son negativos, entonces devuelva el número menos negativo. En todos los demás casos, su solución funcionará perfectamente.

printf("%d\n",max(max_so_far, *max_element(array,array+size))); 

Answer 4

int max_so_far = INT_MIN; 
int max_ending_here = array[0]; 
for (int i = 1; i < size; i++) { 
    max_ending_here = max(max_ending_here + array[i], array[i]); 
    max_so_far = max(max_ending_here, max_so_far); 
} 
printf("%d\n", max_so_far); 

Puede obras

Answer 5

Hacer una ligera además de algo de kadane. Tome un indicador, are_all_elements_negative (establecido en true) y un int (almacene el entero más alto) mientras itera sobre el conjunto, si encuentra un número positivo, establezca el indicador como falso. Mientras que la bandera es verdadera, almacene el número más alto. Al final, revisa el indicador, si el indicador es verdadero, muestra el entero -ve, de lo contrario da salida a la salida regular de algo de Kadane.

Answer 6

El algoritmo de Well Kadane no funciona para el caso cuando todos los elementos de una matriz son negativos. Simplemente devuelve 0 en ese caso. En caso de que si desea el manejo de esto, necesitamos agregar una fase adicional antes de la implementación real. La fase se verá si todos los números son negativos, si son, devolverá el máximo de ellos (o el más pequeño en términos de valor absoluto).

puedo sugerir una implementación

#define find_max_val(x,y) x >= y ?x :y; 

int min_sum(int a[],int n){ 
int min_so_far = a[0],min_end_here = a[0]; 

for(int i = 1;i < n; i++){ 

    min_end_here = find_max_val(a[i],min_end_here + a[i]); 
    min_so_far = find_max_val(min_so_far,min_end_here); 
} 

return min_so_far; 
} 

todavía hay otras implementaciones, dependiendo de cuáles necesitan.

Answer 7

Llego tarde a esta fiesta, pero ¿algo como esto funcionaría?:

cur_sum = max_sum = sequence[0]; 
sum_to_j = 0; 
for j in range(0, len(sequence)): 
    sum_to_j += sequence[j]; 
    if sum_to_j > cur_sum: 
     cur_sum = sum_to_j; 
    if cur_sum > max_sum: 
     max_sum = cur_sum 
    if sum_to_j < 0: 
     sum_to_j = 0; 
     cur_sum = sequence[j]; 
print max_sum; 

Answer 8

Creo que después iba a funcionar: -

int maxSub(vector<int> x){ 
    int sum=x[0],local_max=0; 
    for(int i=0;i<x.size();i++){ 
     local_max+=x[i]; 
     if(sum < local_max) 
      sum=local_max; 
     if(local_max <0) 
      local_max=0; 
    } 
return sum; 

}

Answer 9

Si todos los elementos son negativos, devuelva el elemento más grande por valor

boolean allNegative = true; 
    int bigNegative = Integer.MIN_VALUE; 

    int maxSum = 0; 
    int sum = 0; 
    for(int i=0;i<a.size();i++){ 
     // if all numbers are negative 
     if(a.get(i)>=0){ 
      allNegative = false; 
     }else{ 
     if(a.get(i)>bigNegative){ 
      bigNegative = a.get(i); 
     } 

     } 
    sum += a.get(i); 
    if(sum<0){ 
     sum=0; 
    } 
    if(sum>maxSum){ 
     maxSum = sum; 
    } 

    } 
    if(allNegative){ 
     return bigNegative; 
    } 
    return maxSum; 

Answer 10

Funciona con el siguiente código

public int algorithmKadane(int[] input_array){ 
int sum = input_array[0]; 
int rotate_sum = input_array[0]; 
for(int i=1; i< input_array.length ; i++){ 
rotate_sum = Math.max(input_array[i], rotate_sum+input_array[i]); 
sum = Math.max(rotate_sum,sum); 
} 
return sum; 
} 

Answer 11

Por favor remítase a algoritmo de Kadane wikiped max subarray

int max_subArray(Integer[] input){ 
    int max_so_far,max_ending_here; 
    max_so_far = max_ending_here =input[0]; 

    for(int i =1; i<input.length;i++){ 
     max_ending_here = Math.max(input[i], input[i]+max_ending_here); 
     max_so_far = Math.max(max_so_far, max_ending_here); 
    } 

    return max_so_far;  
} 

y volverá -10 en su caso