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になります。
どうすれば負の数でも機能させることができますか？
ありがとうございました！
すべての要素が負の場合、最大のサブアレイは空のサブアレイであり、合計は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);
ウィキペディアによると、Kadaneのアルゴリズムには少なくとも1つの正の数が必要であるため、すべての負の配列は無効な入力です。
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);
それはうまくいくかもしれません
かだねのアルゴに少し足してください。配列を反復処理するときに、フラグare_all_elements_negative（trueに設定）およびint（最大の-ve整数を格納）を取得します。正の数が見つかった場合は、フラグをfalseに設定します。フラグがtrueの間、最大の-venumを格納します。最後に、フラグをチェックします。フラグがtrueの場合は、-ve整数を出力します。それ以外の場合は、通常のKadaneのアルゴ出力を出力します。
さて、Kadaneのアルゴリズムは、配列のすべての要素が負の場合には機能しません。その場合は単に0を返します。これを処理するために必要な場合は、実際の実装の前に追加のフェーズを追加する必要があります。フェーズは、すべての数値が負であるかどうかを確認します。負の場合は、最大値（または絶対値で最小値）を返します。
1つの実装を提案できます
#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 -2 -5-4-1の場合
最大の合計サブ配列は-1です。
ただのO（n）検索。
コード：
int maxSubArraySum(int array[], int size) {
int max_sum = INT_MIN, max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here += a[i];
if (max_sum < max_ending_here) {
max_sum = max_ending_here;
}
max_ending_here = max(max_ending_here, 0);
}
return max_sum;
}
すべての要素が負の場合、最小の負の数を返します。他のすべての場合、ソリューションは問題なく機能します。
printf("%d\n",max(max_so_far, *max_element(array,array+size)) );
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;
}
wikipedkadaneのアルゴリズムmaxサブアレイを参照してください
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を返します
これはあなたの目標を達成するための別のオプションです
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;
}
これが私のアプローチです、余分な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;
}
私はこのパーティーに遅れていますが、この作品のようなものはありますか？：
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;
すべての要素が負の場合、最大の要素を値で返します
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;
以下のコードで動作します。
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;
}
このソリューションが、Kadaneの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;
}
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;
}
int maxSub(vector<int> x){
int current_max=0,overall_max=INT_MIN;
for(int i=0;i<x.size();i++){
current_max+=x[i];
if(overall_max<current_max)
overall_max=current_max;
if(current_max <0)
current_max=0;
}
return overall_max;
}