递归与分治策略解决最大字段和问题

1、递归与分治策略最大子段和问题1、问题的描述给定由n个整数组成的序列（al,a2,an）,求该序列形如g的子段和的最大值。分治算法就是将一个问题分解成若干个小问题，对若干个小问题分别求解，最后 在合并起来。最大子段问题可以分成三种情况1.数组al-n（bp数组前1至n个元素）的最大子段和aln/2的最大子段相同2数组al-n（w数组前1至n个元素）的最大子段和an/2+l-n的最大子段相同3.数组al-n的最大子段和是由al-n/2和an/2+ln结合而成，求解方法为 则分别求出n/2imaxsak和 max sak,然后将两个值相加即得到此种情况下的数组最大子段和0<二iv二n/2 k=

2、i n/2+l<=iv二n k二 n/2最后分别求出三种情况的最大子段和，再比较三个子段和，最大的那个即为数组 的最大字段和。2、代码及注释include <stdio. h>include <stdlib. h>#include <time h>#define max_n 20 int max3(int, int, int):int maxsubarrayar)s(int );int maxsubarrtiy (ini , int, int);int main()int numsmax_n ；/定义一个最大长度为20的数组 int i;stand (

3、time (0); /随机数产生器printf("array: n");/产生max n个随机数for( i = 0; i < max_n; i卄)随机数产工的规则 numsi = (int) (rand() % (max_n * 2) - max_n);printf(*%dt*, nums订)；printf("n");/调用递归函数printf (z，the max subsequen sum is %d n，z, mcixsubarrayans (nums); return 0; /求三个数中的最大值int max3(int a, int b,

4、 int c) if(a > b)return a > c ? a : c; elsereturn b > c ? b : c;/采用分治策略int maxsubarray (int nums, int left, int right)int maxleftsum, maxrightsum;/左右边的最人和int maxleftbordersum, maxrightbordersum;/含中间边界的左右部分最大和int leftbordersum, rightbordersum;/含中间边界的左右部分当前和/递归到最后的基本悄况if(left = right)if(numsl

5、eft > 0)return nu:elsereturn 0;递归求左右部分最人值int mid = (left + right) / 2, i;maxleftsum 二 maxsubarray(nums, left, mid); maxrightsum 二 mcixsubarray (nums, mid + 1, right):求含中间边界的左部分的最大值maxleftbordersum = 0, leftbordersum = 0;for(i = mid; i >= left; i)leftbordersum +二 numsi;if(leftbordersum > mti

6、xleftbordersum)maxleftbordersum = leftbordersum;求含中间边界的右部分的最大值maxrightbordersum 二 0, rightbordersum 二 0;for(i = mid + 1; i <= right; i+) rightbordersum +二 numsi;i f(ri ghtbordersum > maxrightbordcrsum)maxrightbordersum = rightbordersum;/返回三者中的最大值return max3(maxleftsum, maxrightsum, maxleftbordersum + maxrightbordersum): int mcixsubarrayans (int nums)return maxsubarray(nums, 0, max_n 一 1);3、运行结果产生20个平均分布在0左右的随机故8418-1-10916-10-7-414-1?-418-7131325最大子段和为44.press any key