问题描述：最大连续序列问题。第一行输入要解决的case数，接下来每一行的第一个是序列的元素个数，后面跟着元素；输出最大和与序列号。
Sample Input 2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5 Sample Output Case 1: 14 1 4 Case 2: 7 1 6
本题有多种解法：
1、暴力破解。
2、分治策略。（我用的是分治策略，参考的是算法导论。结果对了，但是始终ac不过。）
#include<stdio.h> #include<string.h> typedef struct { int sum; int low,high; }Max; Max FindMaxSum(int num[],int low, int high); Max FindCrossingMaxSum(int *num,int low,int high); void main(){ int **num; int T,i,j=0,c,sum=0,temp; Max m; scanf("%d",&T); num=(int **)malloc(sizeof(int)*T); for(i=0;i<T;i++){ c=0; j=0; scanf("%d",&temp); num[i]=(int *)malloc(sizeof(int)*(temp+1)); num[i][j++] = temp; while(c != '\n'){ scanf("%d",&temp); num[i][j++] = temp; c = getchar(); } } for(i=0;i<T;i++){ m = FindMaxSum( num[i], 1, num[i][0]); printf("Case %d:\n%d %d %d\n", i+1, m.sum, m.low, m.high); if(i!=T-1) printf("\n"); } } Max FindMaxSum(int *num,int low, int high){ if(high == low){ Max m; m.sum = num[low]; m.low = m.high = low; return m; } else{ int mid = (low + high) / 2; Max left, right, crossing; left = FindMaxSum(num, low, mid); right = FindMaxSum(num, mid+1, high); crossing = FindCrossingMaxSum(num, low, high); if(crossing.sum>=left.sum && crossing.sum>=right.sum) return crossing; else if(left.sum>=right.sum && left.sum >= crossing.sum) return left; else return right; } } Max FindCrossingMaxSum(int *num,int low,int high){ int i,sum=0,MaxLeftSum,MaxRighSum; Max crossing; for(i=(low + high)/2; i>=low; i--){ sum += num[i]; if(sum>=MaxLeftSum){ MaxLeftSum = sum; crossing.low = i; } } sum = 0; for(i=(low + high)/2+1; i<=high; i++){ sum += num[i]; if(sum>=MaxRighSum){ MaxRighSum = sum; crossing.high = i; } } crossing.sum = MaxRighSum + MaxLeftSum; return crossing; } 备忘：（1）动态分配多维数组；
（2）二分算法的递归实现
（3）结构体的应用
3、动态规划。（最优解，仅转载算法思想，）
用数组a表示存储的数字序列，sum表示当前子段和，maxsum表示最大子段和。不妨设想：当sum为负数的时候： 1.当下一个数字a[i]为正数的时候，sum+a[i] < a[i]，不如将sum归零重新计算 2.当下一个数字为负数的时候，sum+a[i]< 0 ，若再下一个数字还为负数，依旧可以得出和小于零……直到遇到一个正数，此时回到1的情况，不如将sum归零计算。 综上所述，当sum为负数的时候，归零。
那么再看sum为正数的时候： 1.当下一个数字a[i]为正数的时候，当然选择加上a[i]，并且可以更新maxsunm； 2.当下一个数字a[i]为负数的时候，由于不知道后面数字的情况，无法做出决策。 综上所述，当sum>maxsum的时候，要更新maxsum，并且一直累加a[i]。
题目还要求输出这个子段的start位置和end位置。可以用x,y分别表示当前最优（大）的子段的开始和结束位置，然后再用sta和ed变量表示当前子段的开始和结束位置。结合上面的叙述： 1.当sum>maxsum的时候，即需要更新的时候，就要更新x和y的位置； 2.当sum< 0的时候，即需要使sum归零计算的时候，就需要把sta的位置置为i+1(指向下一个位置的数字)；
