Алгоритм Кадане Отрицательные числа

Question

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

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

  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

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

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 2

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

Answer 3

Ну, алгоритм Кадане не работает для случая, когда все элементы массива отрицательны.В этом случае он просто возвращает 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 4

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

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