问题描述：给定N个整数序列，{A1,A2,…,An},求该序列中存在的最大的连续n个整数和。

要解决这个问题，我们很容易想到，可以把所有的连续子列和全部算出来，然后从中找出最大的一个即为所求答案，算法代码如下：

原始代码

int maxSubseqSum1(int A[],int N) { int i,j,k; int ThisSum,MaxSum = 0; 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++ ) ThisSum += A[k]; if(ThisSum>MaxSum) MaxSum = ThisSum; } } return MaxSum; }

这个算法很容易想到，当然该算法的时间复杂度也是大的可怕，为T(N)=O(N^3)

仔细分析该算法，发现该算法做了无用功，当j增加1时，我们没有必要从头算起，我们只要在前面i~j的部分和后面加一个元素就行，没有必要重新算前面i~j部分和，也就是说，k循环是多余的。

那我们优化后的代码如下：

优化代码

int maxSubseqSum2(int A[],int N) { int i,j; int ThisSum,MaxSum = 0; for( i = 0; i<N; i++) { /*i是子列左端位置*/ ThisSum = 0;/*ThisSum是从A[i]到A[j]的子列和*/ for( j = i; j<N; j++ ) { /*j是子列右端的位置*/ ThisSum += A[j]; if(ThisSum>MaxSum) MaxSum = ThisSum; } } return MaxSum; }

该算法时间复杂度为T(N) = O(N^2)，较第一个算法快一些。

那还有没有更快的算法了呢？答案是肯定的。我们可以应用分而治之的思想去解决这一道题目。 什么是分而治之呢？参见分而治之。

解题思路：把数组从中间一分为二，然后递归地去解决左右两边的问题，分别得到左右两边的最大子列和，但此时我们还不能下定论，还需要考虑跨越边界的最大子列和，即得到这三个结果，返回其中的最大值。代码如下

分而治之法

int Max(int A, int B, int C) { /*return A > B ? A > C ? A :C: B > C ? B : C;*/ if (A > B) { if (A > C) return A; else return C; } else if (B > C) return B; else return C; } int DivideAndConquer(int List[], int left, int right) { int MaxLeftSum, MaxRightSum; int MaxLeftBoardSum, MaxRightBoardSum; int LeftBoardSum, RightBoardSum; int center,i; /*递归终止条件*/ if (left == right) { if (List[left] > 0) return List[left]; else return 0; } center = (right + left) / 2; MaxLeftSum = DivideAndConquer(List, left, center); MaxRightSum= DivideAndConquer(List, center+1, right); MaxLeftBoardSum = 0; LeftBoardSum = 0; for (i = center;i >= left; i--) LeftBoardSum += List[i]; if (LeftBoardSum > MaxLeftBoardSum) MaxLeftBoardSum = LeftBoardSum; MaxRightBoardSum = 0; RightBoardSum = 0; for (i = center + 1; i <= right; i++) RightBoardSum += List[i]; if (RightBoardSum > MaxRightBoardSum) MaxRightBoardSum = RightBoardSum; return Max(MaxLeftSum, MaxRightSum, MaxRightBoardSum + MaxLeftBoardSum); } int maxsequence3(int A[], int N) { return DivideAndConquer(A, 0, N-1); }

该算法的时间复杂度为T(N)=O(N*logN)，较之前两个有很大改进。

总结

把一个大规模的问题，化简为几个小问题，分别解决每个小问题，我们便可以轻松得到问题的答案。由此可见递归的思想的重要性。

最后，祝愿所有女性朋友们女神节快乐！

—Alisa 写于 江苏泰州 2017.03.08