这个程序使用分治法计算最大子段，结果为最大子段之和，用递归程序实现。
原始数据使用随机函数生成。
采用结构化程序设计，可以很容易改为从标准输入或文件读入数据，只需要修改函数getData即可。
数据个数由宏定义给出，也可以轻松地改为输入 。
/* * 最大子段算法程序 */#include关键代码：#include #include #define N 13void getData(int [], int);int maxsumfun(int a[], int left, int right);int main(void){ int a[N], i; getData(a, N); /* 获得数据放入数组a中 */ printf("datas: "); for (i = 0; i < N; i++) printf("%d ", a[i]); printf("\n"); int ms; ms = maxsumfun(a, 0, N - 1); printf("maxsum=%d\n", ms); return 0;}int maxsumfun(int a[], int left, int right){ int maxsum = 0; if(left == right) { if(a[left] > 0) maxsum = a[left]; else maxsum = 0; } else { int mid, leftsum, rightsum, midsum; mid = (left + right) / 2; leftsum = maxsumfun(a, left, mid); rightsum = maxsumfun(a, mid+1, right); int leftsum1 = 0; int lefts = 0; int i; for(i=mid; i>=left; i--) { lefts += a[i]; if(lefts > leftsum1) leftsum1 = lefts; } int rightsum1 = 0; int rights = 0; for(i=mid+1; i<=right; i++) { rights += a[i]; if(rights > rightsum1) rightsum1 = rights; } midsum = leftsum1 + rightsum1; if(midsum < leftsum) maxsum = leftsum; else maxsum = midsum; if(maxsum < rightsum) maxsum = rightsum; } return maxsum;}void getData(int d[], int n){ time_t t; srand((unsigned) time(&t)); /* 设置随机数起始值 */ int i; for(i=0; i < n; i++) d[i] = rand() % 30 - 10; /* 获得-10--20之间的整数值 */}
// 递归计算最大子段int maxsumfun(int a[], int left, int right){ int maxsum = 0; if(left == right) { if(a[left] > 0) maxsum = a[left]; else maxsum = 0; } else { int mid, leftsum, rightsum, midsum; mid = (left + right) / 2; leftsum = maxsumfun(a, left, mid); rightsum = maxsumfun(a, mid+1, right); int leftsum1 = 0; int lefts = 0; int i; for(i=mid; i>=left; i--) { lefts += a[i]; if(lefts > leftsum1) leftsum1 = lefts; } int rightsum1 = 0; int rights = 0; for(i=mid+1; i<=right; i++) { rights += a[i]; if(rights > rightsum1) rightsum1 = rights; } midsum = leftsum1 + rightsum1; if(midsum < leftsum) maxsum = leftsum; else maxsum = midsum; if(maxsum < rightsum) maxsum = rightsum; } return maxsum;}