虽然写的非常差但还是我这个小白自己亲手写出来的，一边翻书一边谷歌..... 花了好多小时，虽然很罗嗦而且希望大家能帮我找一下我的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;
}
