darkflammme 2018-03-01 11:44 采纳率: 100%

# 递归 算法 最大子数组

#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条回答默认 最新

• threenewbee 2018-03-01 14:55
关注
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 悬赏问题

• ¥30 DeepLung肺结节检测生成最大froc值对应的epoch报错
• ¥50 滴滴出行模拟系统，模拟叫车、出行过程等过程
• ¥15 信号发生器如何将频率调大，步尽值改成10
• ¥15 keil 5 编程智能家具，风扇台灯开关，人体感应等
• ¥100 找一名渗透方面的专家
• ¥20 使用Matlab gui设计一个插补小程序
• ¥15 evo评估时曲线出现问题
• ¥15 eNSP拓扑图配置实验
• ¥20 有没有兄弟会替换fmod studio的.bank文件内的音效？
• ¥20 如何解决访问网址被屏蔽的情况