最大连续子数列
在线处理法在线处理法
#include < stdio.h> int main() { int arry[11]; int x, Maxsum = 0, Thissum = 0; for (x = 0; x <= 10; x++) { scanf("%d", &arry[x]); Thissum += arry[x]; if (Thissum > Maxsum)Maxsum = Thissum; else if (Thissum < 0)Thissum = 0; } printf("%d", Maxsum); return 0; }
从左往右开始扫描,若现在的Thissum为负数就丢弃,比较大就替代。
分而治之的递归算法
#include< stdio.h> int Maxs(int x, int y, int z) { return x > y ? x > z ? x : z : y > z ? y : z; } int Maxsum(int left, int right, int arry[]) { if (left == right) if (arry[right] < 0)return 0; else return arry[right];//从最小的单个数才开始计算 int rightsum = 0, leftsum = 0, center = (left + right) / 2; int sum = 0,maxsumright=0,maxsumleft=0; //需要比较中间线左边的最大和右边的最大以及横跨中间线的最大 rightsum = Maxsum(center+1, right, arry); leftsum = Maxsum(left, center, arry); int i; for (i = center; i >= left; i--) { sum += arry[i]; if (sum > maxsumleft)maxsumleft = sum; }//先计算从中间线开始左边的最大值 sum = 0; for (i = center + 1; i <= right; i++) { sum += arry[i]; if (sum > maxsumright)maxsumright = sum; }//再计算右边最大值注意是连续的 return Maxs(leftsum, rightsum, maxsumleft + maxsumright); } int main() { int arry[101]; int i, j; scanf("%d", &j); for (i = 0; i <= j-1; i++) { scanf("%d", &arry[i]); } printf("%d", Maxsum(0, j - 1, arry)); return 0; }
![大概流程](https://raw.githubusercontent.com/LINGyue-dot/a-mass-of-photos/master/blog/%E5%88%86%E8%80%8C%E6%B2%BB%E4%B9%8B.png)
大概流程