给定整数A1，A2，...An（可能为负数），求子序列和最大值（如果所有整数为负数，则子序列和为0）。
穷举法
int MaxSubsequenceSum2(const int A[], int N) {
int MaxSum = 0;
for (int i = 0; i < N; i++ ) { /*1*/
int ThisSum = 0;
/*
内层循环 每次遍历元素 然后计算从前面数值的和，
然后比较，获得以该元素为起点的最大值。
*/
for (int j = i; j < N; j++ ) { /*2*/
ThisSum += A[j];
if (ThisSum > MaxSum) {
MaxSum = ThisSum;
}
}
}
return MaxSum;
}
画了一个简单的实例图，辅助理解，主要是做两次循环遍历，内层遍历是 以当前元素为起点，查找到最大子序列和，外层循环，寻找每次以每个元素为起点的最大值。这个方法时间复杂度O(n2)。
1
分治法
分治法的主要思想是把问题分成两个大致相等的字问题，然后递归地对它们求解，这是“分”问题。“治”阶段将两个子问题的解合并到一起，再做些少量的附加工作，最后得到整个问题的解。
还是先上代码。代码有点长，需要慢慢看。
int MaxSubSum(const int A[], int Left, int Right) {
int MaxLeftSum, MaxRightSum;
int MaxLeftBorderSum, MaxRightBorderSum;
int LeftBorderSum, RightBorderSum;
// 基础情况
if (Left == Right) {
if (A[Left] > 0) {
return A[Left];
} else {
return 0;
}
}
// 递归计算
int Center = (Left + Right) / 2;
MaxLeftSum = MaxSubSum(A, Left, Center);
MaxRightSum = MaxSubSum(A, Center+1, Right);
// 计算出中间部分向右 最大连续序列和
MaxLeftBorderSum = 0;
LeftBorderSum = 0;
for (int i = Center; i >= Left; i--) {
LeftBorderSum += A[i];
if (LeftBorderSum > MaxLeftBorderSum) {
MaxLeftBorderSum = LeftBorderSum;
}
}
// 计算出中间部分向右 最大连续序列和
MaxRightBorderSum = 0;
RightBorderSum = 0;
for (int i = Center+1; i <= Right; i++) {
RightBorderSum += A[i];
if (RightBorderSum > MaxRightBorderSum) {
MaxRightBorderSum = RightBorderSum;
}
}
// 获得三个部分中最大值
int max = MaxLeftSum > MaxRightSum ? MaxLeftSum : MaxRightSum;
int borderMax = MaxLeftBorderSum + MaxRightBorderSum;
max = max > borderMax ? max : borderMax;
return max;
}
int MaxSubsequenceSum3(const int A[], int N) {
return MaxSubSum(A, 0, N-1);
}
这个问题中，最大子序列和可能出现在三个位置。前半部分，后半部分，或者跨越前后部分。如果是跨越前后部分，那么肯定是从中间向左右两边的最大值的和。
算法大概有二个部分，一个基准条件，如果只剩下一个元素,则就是当前元素了，这也是递归必备的条件。第二部分是递归计算左边最大值，右边最大值，以及从中间向左和从中间向右的最大值（即跨越前后部分）和。
2
联机算法
联机算法，它只对数据进行一次扫描，一旦被读入并处理，它就不需要被记忆。在任何时刻，算法都可以给出已经读入的数据给出正确答案。
先展示代码
int MaxSubsequenceSum4(const int A[], int N) {
int ThisSum, MaxSum;
ThisSum = MaxSum = 0;
for (int i = 0; i < N; i++) {
ThisSum += A[i];
if (ThisSum > MaxSum) {
MaxSum = ThisSum;
} else if (ThisSum < 0) { /*1*/
ThisSum = 0;
}
}
return MaxSum;
}
核心思想:要求最大子序列和，那么前面部分序列的和如果小于0，那么包含该序列和肯定不是最大的（包含该序列，那么和肯定会减少）。
最后，最近开始认真的学习一遍算法部分，也尝试着把学习的东西记录下来，也是让自己更好的理解。算是一个简单的开篇，下篇写写排序部分，算是挖个坑。
参考
- 数据结构与算法分析：C语言描述 2.4.3节
- 算法导论
