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によると、Kadaneのアルゴリズムは、少なくとも一つの正の数を必要とするので、あなたのすべての負の配列が無効な入力です。

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のALGOに若干の追加を行います。 配列を反復処理しているときに正の数を見つけた場合、 、フラグを取る（trueに設定）are_all_elements_negativeとINT（最高-ve整数を格納し）、フラグはfalseを設定します。 フラグがtrueの間は、-veの最大値を格納します。最後にフラグをチェックし、フラグが真であれば-ve整数を出力し、そうでない場合は通常のKadaneのalgo出力を出力します。配列のすべての要素が負の場合

Answer 6

まあKadaneのアルゴリズムは、ケースのために動作しません。その場合、単に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

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

kadaneのアルゴリズムをwikipedを参照してくださいそして、それが返されます-10あなたのケース