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

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.

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

Спасибо!

24

c++ algorithm kadanes-algorithm

Источник

user996056 30 мар '12 в 11:40

18 ответов

Решение

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

72

Источник

user265592 30 мар '12 в 11:58

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

Может работает

5

Источник

user2243406 12 июл '13 в 02:35

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

4

Источник

user1495868 12 июл '13 в 15:19

Если у нас есть массив всех негативов, то результатом будет максимальный элемент в массиве.
Например: если элементы массива равны
-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; 
}

3

Источник

user6185191 11 май '19 в 21:49

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

Есть еще другие реализации в зависимости от потребностей.

3

Источник

user1827561 15 окт '13 в 21:37

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

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

1

Источник

user610856 30 мар '12 в 12:03

Согласно WIKI

public int maxSubArray(int[] nums) {
    int currentSum = 0;
    int bestSum = 0;

    for (int element : nums) {
        currentSum = Math.max(0, currentSum + element);
        bestSum = Math.max(bestSum, currentSum);
    }

    return bestSum;
}

Приведенный выше код не будет вводить

nums = [-1]

Согласно WIKI снова

Эта версия алгоритма вернет 0, если вход не содержит положительных элементов (в том числе, когда вход пуст). Для варианта проблемы, который запрещает пустые подмассивы, вместо этого best_sum следует инициализировать отрицательной бесконечностью, а также в цикле for current_sum следует обновить как max(x, current_sum + x). В этом случае, если входные данные не содержат положительного элемента, возвращаемое значение - это значение самого большого элемента (т. Е. Наименьшее отрицательное значение) или отрицательная бесконечность, если вход был пуст.

Измененный код для отрицательных входов:

public int maxSubArray(int[] nums) {
    int currentSum = 0;
    int bestSum = Integer.MIN_VALUE;

    for (int element : nums) {
        currentSum = Math.max(element, currentSum + element);
        bestSum = Math.max(bestSum, currentSum);
    }

    return bestSum;
}

1

Источник

user5556298 19 апр '20 в 06:10

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

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

1

Источник

user11751134 07 июл '19 в 19:53

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

0

Источник

user1115422 17 янв '18 в 09:52

Обратитесь к этому превосходному объяснению алгоритма Кадане, который будет работать и для всех отрицательных чисел.

goреализация здесь:

      func maxSubArrayKadane(nums []int) int {
    // Validate input
    var n = len(nums)
    if n == 0 {
        return 0
    }
    if n == 1 {
        return nums[0]
    }

    var localMax = 0
    var globalMax = math.MinInt
    for _, val := range nums {
        localMax = max(val, localMax+val)
        if localMax > globalMax {
            globalMax = localMax
        }
    }
    return globalMax
}

func max[T constraints.Ordered](a, b T) T {
    if a > b {
        return a
    }
    return b
}

0

Источник

user7239138 05 авг '22 в 11:37

Вот мой подход, использовал дополнительные 2 переменные

      public int maxSubArray(int[] nums) {
  int max_so_far = 0;
  int max_ends_here = 0;
  int largestNeagtive = Integer.MIN_VALUE;
  boolean isAllNegativeNumbers = true;
    
  for (int i = 0; i < nums.length; i++) {
    max_ends_here += nums[i];      
    if (max_ends_here < 0) max_ends_here = 0;
    if (max_so_far < max_ends_here) max_so_far = max_ends_here;
    if (isAllNegativeNumbers && nums[i] >= 0) isAllNegativeNumbers = false;
    if (nums[i] < 0  && nums[i] > largestNeagtive) largestNeagtive = nums[i];
  }
  return isAllNegativeNumbers ? largestNeagtive : max_so_far;
}

0

Источник

user10249156 16 окт '21 в 19:17

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

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;

-1

Источник

user4429574 12 мар '15 в 17:25

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

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

-1

Источник

user5379704 17 дек '17 в 23:30

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

    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;

-1

Источник

user4681856 07 сен '16 в 10:51

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

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

-1

Источник

user10940281 20 янв '19 в 17:51

              public static int max_sum(int[] in){

        int maxsum=0;
        int cursum=0;
        for (int i=0;i<in.length;i++){
            cursum = in[i]+cursum;
            if (cursum>maxsum) {
                maxsum = cursum;
            }

//            for negative value
            if (cursum < 0) {
                for (int n=0;n<in.length;n++){
                    maxsum = in[n];
                    if (cursum>maxsum){
                        maxsum=cursum;
                    }
                }
            }
        }
        return maxsum;
    }

-1

Источник

user10679698 16 апр '21 в 12:46

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

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;

}

-2

Источник

user5793086 27 май '16 в 19:59

Другие вопросы по тегам c++ algorithm kadanes-algorithm

user21441 30 мар '12 в 11:48 2012-03-30 11:48 · Accepted Answer · 2012-03-30 11:48

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

32

Источник

user21441 30 мар '12 в 11:48