Kadane algoritmo numeri negativi

Question

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

Se avessi tale matrice, la mia implementazione dell'algoritmo Kadane per trovare la massima sottoarray opere:

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

Tuttavia, se ho un array di tutti negativi:

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

Non funzionerà, dovrebbe restituire -10, ma ottengo 0.

Come posso farlo funzionare anche per i numeri negativi?

Grazie!

Answer 1

In base a Wikipedia, l'algoritmo di Kadane richiede almeno un numero positivo, quindi l'array tutto negativo non è valido.

Answer 2

Quando tutti gli elementi sono negativi, il sottoarray massima è il sottoarray vuoto, che ha somma 0.

Ma se si vuole modificare l'algoritmo per memorizzare il più grande elemento in questo caso, si potrebbe procedere come segue:

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

Se tutti gli elementi sono negativi, restituire il numero meno negativo. In tutti gli altri casi, la soluzione funzionerà perfettamente.

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

Può funziona

Answer 5

fare una piccola aggiunta al algo di Kadane. Prendete una bandiera, are_all_elements_negative (impostata su true) ed un int (memorizzare il più alto numero intero ve) mentre l'iterazione di matrice, se si trova un numero positivo, impostare il flag falso. Mentre il flag è true, memorizza il numero -ve più alto. Alla fine, controlla il flag, se il flag è true, emette il valore intero -ve, altrimenti restituisce l'output regolare di Kadane. L'algoritmo di

Answer 6

Beh Kadane non funziona per il caso in cui tutti gli elementi di un array sono negativi. In questo caso restituisce semplicemente 0. Nel caso in cui se si desidera che per la gestione di questo, è necessario aggiungere una fase extra prima dell'implementazione effettiva. La fase apparirà se tutti i numeri sono negativi, se lo sono restituiranno il massimo (o il più piccolo in termini di valore assoluto).

posso suggerire un'implementazione

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

ci sono ancora altre implementazioni a seconda quelli hanno bisogno.

Answer 7

Sono in ritardo per questa festa, ma vorrei qualcosa di simile a questo lavoro?:

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

Penso che segue potrebbe funzionare: -

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

Se tutti gli elementi sono negativi, riportare l'elemento più grande per valore

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

Funziona con il codice qui sotto.

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

Si prega di fare riferimento al algoritmo di 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;  
} 

E tornerà -10 nel tuo caso