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

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

Когда все элементы отрицательны, максимальный подмассив - это пустой подмассив с суммой 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 2

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

Answer 3

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

Answer 4

Это еще один вариант для достижения вашей цели

int Solution::maxSubArray(const vector<int> &A){
    int cs=0,ms=0,l=A.size(),x=0,min;
    if(A[0]<0)
        min=A[0];
        x++;
    if(l==1)
        return A[0];
    for(int i=1;i<A.size();i++){
        if(A[i]<0)
            x++;
        if(A[i]>min)
            min=A[i];
        else
            break;
      }
    if(x==l)
        return min;
    for(int i=0;i<A.size();i++){
        cs=cs+A[i];
        if(cs<0)
        cs=0;
        ms=max(cs,ms);
    }
return ms;
}

Answer 5

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 6

если у нас есть массив всех негативов, то результатом будет элемент max в массиве.
Например: если элементы массива
-3 -2 -5 -4 -1

Самая большая сумма подмассива равна -1.

Мы можем добавить эту проверку и посмотреть, возвращает ли функция Кадане 0.
(просто O (n) поиск. Не изменит сложность времени :))

Код:

int maxSubArraySum(int a[], int size) { 
    int max_so_far = INT_MIN, max_ending_here = 0, max_negative_scenario = INT_MIN; 

    for (int i = 0; i < size; i++) { 
        max_ending_here = max_ending_here + a[i]; 
        if (max_so_far < max_ending_here) 
            max_so_far = max_ending_here; 

        if (max_ending_here < 0){ 
            max_ending_here = 0; 

        if(a[i] > max_negative_scenario) // additional check
            max_negative_scenario = a[i];
    } 
    if(max_so_far == 0) // additional check
        max_so_far = max_negative_scenario;
    return max_so_far; 
} 

Answer 7

Надеюсь, что это решение будет работать и для всех случаев с отрицательными числами для алгоритма Кадане

    long long int n,max_f=0,i,max_end=0,s;
    cin>>n;
    long long int a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    long long int *m;
    m=max_element(a,a+n);
    if(*m<0)
    {
        s=*m;

    }
    else {

        for(i=0;i<n;i++)
        {
            max_end= max_end +a[i];
            if(max_end<0)
            {
                max_end=0;
            }
            if(max_f < max_end)
            {
            max_f=max_end;
            }
            s=max_f;
        }
    }
    cout<<s<<endl;
}

Answer 8

Пожалуйста, обратитесь к алгоритму Википеда Кадане Макс. Подмассив

 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 в вашем случае

Answer 9

Работает с кодом ниже.

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 10

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

    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;