Kadane Алгоритм отрицательных числа

Question

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

Если бы я имел этот массив, моя реализация алгоритма Kadane найти максимальный подмассив работы:

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

Однако, если у меня есть массив всех негативов:

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

Это не сработает, он должен вернуться -10, но я получаю 0.

Как я могу заставить его работать для отрицательного числа тоже?

Спасибо!

Answer 1

Согласно Wikipedia, алгоритму Кадана требуется хотя бы одно положительное число, поэтому ваш отрицательный массив является недопустимым.

Answer 2

Когда все элементы отрицательны, максимальная подмассив является пустым подмассивом, который имеет сумму 0.

Но если вы хотите изменить алгоритм, чтобы сохранить наибольший элемент в этом случае, вы можете сделать следующее:

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

Если все элементы отрицательные, верните наименьшее отрицательное число. Во всех остальных случаях ваше решение будет работать нормально.

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

Он может работает

Answer 5

сделать небольшое дополнение к Kadane в алгоритме. Возьмите флаг, are_all_elements_negative (установите значение true) и int (сохраните наивысшее значение -ve integer) , итерации по массиву, если вы найдете положительное число, установите флаг false. Пока флаг имеет значение true, сохраните наивысшее значение -ve num. В конце проверьте флаг, если флаг имеет значение true, выведите значение -ve integer, иначе выведите обычный выход из файла Kadane.

Answer 6

Хорошо алгоритм Кадане не работает для случая, когда все элементы массива отрицательны. Он просто возвращает 0 в этом случае. В случае если вы хотите, чтобы для обработки этого нам нужно добавить дополнительную фазу до фактической реализации. Эта фаза будет выглядеть, если все числа отрицательные, если они будут, они вернут максимум из них (или наименьший по абсолютной величине).

Я могу предложить один реализация

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

есть еще и другие варианты реализации в зависимости от них нужно.

Answer 7

Я опаздываю на эту вечеринку, но что-то вроде этой работы?:

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

Я думаю, что следующий будет работать: -

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

Если все элементы отрицательны, возвращенная наибольший элемент по значению

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

Он работает с ниже код.

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

Пожалуйста, обратитесь к алгоритму wikiped kadane в 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;  
} 

И он вернется -10 в вашем случае