递归 算法 最大子数组

虽然写的非常差但还是我这个小白自己亲手写出来的,一边翻书一边谷歌..... 花了好多小时,虽然很罗嗦而且希望大家能帮我找一下我的find_maximum_subarry的错误,其余两个函数我都试过了应该是对的

#include

typedef struct all_of_sum
{
int aa;
int bb;
int cc;
}all_sum;
all_sum all;

int max(int one, int two, int three)
{
int current_max = one;
if(current_max < two)
{
current_max = two;
if(current_max < three)
current_max = three;
}
else if(current_max >= three)
{
if(current_max < three)
current_max = three;
}

return current_max;

}

all_sum find_crossing_sum(int *array,int a,int mid,int b)
{
int maxleftsum = -999999,maxrightsum = -999999,currentleft = 0;
int currentright = 0,i = 0,j = 0;

for(i = a; i <=mid;i++)
{
    currentleft = currentleft + array[i];
    if(currentleft > maxleftsum)
        maxleftsum  = currentleft;
    };

for(j = mid+1; j <= b;j++)
{
    currentright = currentright + array[j];
    if(currentright > maxrightsum)
        maxrightsum  = currentright;
    };
all.aa = i-1;
all.bb = j-1;
all.cc = maxleftsum + maxrightsum;

return all;

}

typedef struct find_maxium
{
int low;
int high;
int ddd;
} maxium;
maxium mm;

maxium find_maximum_subarry(int*array,int a,int b)
{
int mid = 0,left_low = 0,left_high = 0,left_sum = 0;
int right_low = 0,right_high = 0,right_sum = 0;
int cross_low = 0,cross_high = 0,cross_sum = 0;
if(a == b)
{
mm.low = a;
mm.high = b;
mm.ddd = array[a];
return mm;
}
else
{
mid = (a + b)/2;
left_low = find_maximum_subarry(array,a,mid).low;
left_high = find_maximum_subarry(array,a,mid).high;
left_sum = find_maximum_subarry(array,a,mid).ddd;

     right_low = find_maximum_subarry(array,mid+1,b).low;
     right_high = find_maximum_subarry(array,mid+1,b).high;
     right_sum = find_maximum_subarry(array,mid+1,b).ddd;

    cross_low = find_crossing_sum(array,a,mid,b).aa;
    cross_high = find_crossing_sum(array,a,mid,b).bb;
    cross_low = find_crossing_sum(array,a,mid,b).cc;
}
if(max(left_sum,right_sum,cross_sum) == left_sum)
    {
        mm.low = left_low;
        mm.high = left_high;
        mm.ddd = left_sum;
    }
else if(max(left_sum,right_sum,cross_sum) == right_sum)
    {
        mm.low = right_low;
        mm.high = right_high;
        mm.ddd = right_sum;
    }
else if(max(left_sum,right_sum,cross_sum) == cross_sum)
    {
        mm.low = cross_low;
        mm.high = cross_high;
        mm.ddd = cross_sum;
    }
return mm;
}

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐