提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
最大子列和问题非常常见。该问题的解法根据时间复杂度有四种解法。下面我会具体阐述这四种解法
该解法时间复杂度为O(n3)，即：用三层循环。思路是：第一层循环确定子列左端位置，第二层循环确定子列右端位置，第三层循环将第一层循环确定的子列左端A[i]到第二层循环确定的子列右端A[j]的每一个值相加并赋值给ThisSum 。赋值完后跳出第三层循环，在第二层循环中与MaxSum进行比较，如果刚得到的这个子列和更大，则更新MaxSum的结果。以此循环之后可得到最大子列和。
int MaxSubseqSum1( int A[], int N ) { int ThisSum, MaxSum = 0; int i, j, k; for( i = 0; i < N; i++ ) { /* i是子列左端位置 */ for( j = i; j < N; j++ ) { /* j是子列右端位置 */ ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */ for( k = i; k <= j; k++ )/* 求A[i]到A[j]的和并赋值给ThisSum */ ThisSum += A[k]; if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */ MaxSum = ThisSum; /* 则更新结果 */ } /* j循环结束 */ } /* i循环结束 */ return MaxSum; }这个方法所需要的时间非常多，所以在N的值过大时，非常不推荐。
该解法时间复杂度为O(n2)，即：用两层循环。这个解法其实是解法一的小小改进。你们想一想，对于这解法一，真的有必要进行第三层循环吗？想一想：对于相同的i，不同的j，我们为什么要在第三层循环中重新将A[i]到A[j]的每一个值相加呢？为什么不直接在上一次循环得到的A[i]到A[j]的和基础上累加1项呢？* 也就是说：对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可
int MaxSubseqSum2( int A[], int N ) { int ThisSum, MaxSum = 0; int i, j; for( i = 0; i < N; i++ ) { /* i是子列左端位置 */ ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */ for( j = i; j < N; j++ ) { /* j是子列右端位置 */ ThisSum += A[j]; /*对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可*/ if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */ MaxSum = ThisSum; /* 则更新结果 */ } /* j循环结束 */ } /* i循环结束 */ return MaxSum; }该解法对于解法一有了长足的提高，但我们有没有其他解法，将该问题的解法的时间复杂再降低呢？
先用两张图表示一下啥叫分而治之。
意思就是：第一步我们先从中间把这个数列一分为二，然后再递归解决左半边，在递归的进入左半边时，我们继续把它一分为二，继续的递归到左半边，继续的一分为二…直到只剩下一个。如下图：分到最后只剩下一个4，这时候最大子列和就是4。而4的右边是一个负数，所以我们应该返回0，跨越这个边界的最大和也是4，所以解决这个子问题，它放回的解是4. 类似的，我们去解决右半边，他返回的结果是5. 对于这4个数字而言，我们还要算一个跨越边界的最大和： 先看左边的两个，他们的子列和有两个，分别是-3和1（注意是跨越边界的最大和，因为要跨越中间橙色的边界，所以不能是4），右边的子列和也是有两个，分别是5和3，于是我们得到跨越边界的最大和为1+5=6. 类似的，对于红色分界线的右边，我们也像上述那样找到它的最大子列和为2+6=8。
这时候就要再求下图的跨越边界的最大和 于是我们就得到了结果：6-2-1+8=11 相信大家应该对这个解法有了思路。那用代码怎么实现呢？代码如下：
int Max3( int A, int B, int C ) { /* 返回3个整数中的最大值 */ return A > B ? A > C ? A : C : B > C ? B : C; } int DivideAndConquer( int List[], int left, int right ) { /* 分治法求List[left]到List[right]的最大子列和 */ int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */ int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/ int LeftBorderSum, RightBorderSum; int center, i; if( left == right ) { /* 递归的终止条件，子列只有1个数字 */ if( List[left] > 0 ) return List[left]; else return 0; } /* 下面是"分"的过程 */ center = ( left + right ) / 2; /* 找到中分点 */ /* 递归求得两边子列的最大和 */ MaxLeftSum = DivideAndConquer( List, left, center ); MaxRightSum = DivideAndConquer( List, center+1, right ); /* 下面求跨分界线的最大子列和 */ MaxLeftBorderSum = 0; LeftBorderSum = 0; for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */ LeftBorderSum += List[i]; if( LeftBorderSum > MaxLeftBorderSum ) MaxLeftBorderSum = LeftBorderSum; } /* 左边扫描结束 */ MaxRightBorderSum = 0; RightBorderSum = 0; for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */ RightBorderSum += List[i]; if( RightBorderSum > MaxRightBorderSum ) MaxRightBorderSum = RightBorderSum; } /* 右边扫描结束 */ /* 下面返回"治"的结果 */ return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum ); } int MaxSubseqSum3( int List[], int N ) { /* 保持与前2种算法相同的函数接口 */ return DivideAndConquer( List, 0, N-1 ); }时间复杂度如下：
“在线”的意思是指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。 在这道题中，我从第一个数值开始向右累加，发现更大和则更新当前结果，如果经过累加之后发现当前的子列和是负数的，那么直接抛弃它，直接从下一个数开始算起，重新累加。因为当前子列和是负数的，往后不管加什么数，它都让后面的数变小，不可能变大，所以不如抛弃它，重头开始。 这个解法快的原因就是利用了这一点：一旦当前子列和是负数的，那么它就没用了，直接抛弃就好了，重新开始扫描下一个。 代码如下：
int MaxSubseqSum4( int A[], int N ) { int ThisSum, MaxSum; int i; ThisSum = MaxSum = 0; for( i = 0; i < N; i++ ) { ThisSum += A[i]; /* 向右累加 */ if( ThisSum > MaxSum ) MaxSum = ThisSum; /* 发现更大和则更新当前结果 */ else if( ThisSum < 0 ) /* 如果当前子列和为负 */ ThisSum = 0; /* 则不可能使后面的部分和增大，抛弃之 */ } return MaxSum; }这个解法是最快的，只有一层循环，所以时间复杂度很明显就是O(n)。
