Kadaně Algorytm Liczby ujemne

Question

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

Gdybym miał tę tablicę, moja implementacja algorytmu Kadaně aby znaleźć maksymalną subarray działa:

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

Jednak jeśli mam tablicę wszystkich negatywów:

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

To nie zadziała, powinno wrócić - 10, ale dostaję 0.

Jak mogę sprawić, aby działał na numery ujemne?

Dziękujemy!

Answer 1

Zgodnie z Wikipedia Algorytm Kadane wymaga co najmniej jednej liczby dodatniej, więc wszystkie ujemne tablice są nieprawidłowe.

Answer 2

Kiedy wszystkie elementy są ujemne, maksymalna subarray jest pusty subarray, która ma sumę 0.

Ale jeśli chcesz zmienić algorytm do przechowywania największy element, w tym przypadku, można wykonać następujące czynności:

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

Jeśli wszystkie elementy są ujemne, to należy zwrócić najmniej ujemną liczbę. We wszystkich innych przypadkach twoje rozwiązanie będzie działało dobrze.

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

Może ona działa

Answer 5

Zrób niewielki dodatek do algo Kadaně użytkownika. Weź flagę, are_all_elements_negative (ustawiona na true) i int (przechowuj najwyższą -ve liczbę całkowitą) podczas iteracji po tablicy, jeśli znajdziesz liczbę dodatnią, ustaw flagę jako false. Podczas gdy flaga jest prawdziwa, przechowuj najwyższą -ve num. Na końcu sprawdź flagę, jeśli flaga jest prawdziwa, wypisz -ve liczbę całkowitą, w przeciwnym razie wypisz normalne wyjście Kadane'a.

Answer 6

Algorytm Well Kadane nie działa w przypadku, gdy wszystkie elementy tablicy są ujemne. W tym przypadku po prostu zwraca 0. W przypadku, gdybyś chciał, żeby to potraktowano, musimy dodać dodatkową fazę przed rzeczywistą implementacją. Faza będzie wyglądać, jeśli wszystkie liczby są ujemne, jeśli są one zwracają maksimum z nich (lub najmniejsze pod względem wartości bezwzględnej).

mogę zasugerować jeden realizacja

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

istnieją jeszcze inne implementacje mogą wynikać te potrzebują.

Answer 7

Spóźniam się na to przyjęcie, ale czy coś takiego dział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

myślę następujących będzie działać: -

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

Jeśli wszystkie elementy są negatywne, należy zwrócić największą elementu o wartości

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

Współpracuje z poniższy kod.

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

Proszę odnieść się do algorytmu wikiped Kadaně za 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;  
} 

I powróci -10 w przypadku