例题：最大子序列和（Maximum subsequence sum） 题意：给定一个序列，找到连续序列的和为最大的序列之和。
方法一：在线处理法 < 最快方法，时间复杂度为O（N）>
思路： 在读入数据的同时，进行求和计算，利用一个变量Maxsum 来保存上一个所计算的和, 设置另一个变量Thissum来储存持续相加得到的和，通过比较这两个变量，来决定是否更新Maxsum，大于则更新，反之不变,同时判断Thissum是否小于0，小于0则，重置为0.
步骤： 1，输入数组 2，输入数组的同时进行求和运算， 3，持续比较上一次找到的最大和值与此时的最大和值的关系，大于则 更新Maxsum，小于则不变 4，接着判断此时的和值是否小于0，小于则将和值重置为0（和为负数的值全部抛弃）。 5，输出最大和值Maxsum即可。 第四步的原因： 解释：当和出现负数时，若持续进行和运算，只会将后面的数值变得更小，远不如我重新开始求和运算的数值大，因此，只要是前面求和运算为负数，那么就直接抛弃，若序列第一个数值为负也是一样的道理，直接抛弃，Thissum依旧为0，若是相加的运算中出现负数，则在这之前的数值都舍弃不要，重新来过，从0开始。
总结：该算法之所以可以达到O（N）的时间复杂度，就是基于第四步，将算法优化，线性即可解决，相比于下面两个方法，
//代码实现： # include<iostream> # define Max 100010 using namespace std; int main() { //读入该序列长度 int n; cin >> n; //定义一个数组存放该序列 int a[Max]; //初始化为0 int Maxsum = 0, Thissum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; Thissum += a[i]; if (Thissum > Maxsum) { //此时和值大于上一个最大和值时，更新Maxsum的值 Maxsum = Thissum; } else if (Thissum < 0) { //当和值出现小于0的情况时，将此时的和值重置为0 Thissum = 0; } } //以上操作完成后，输出Maxsum即可 cout << Maxsum << endl; }方法二：分而治之（时间复杂度 O(Nlog(N)) ）
思路：利用递归，将该序列不断分成两半，分别在左边，右边，比及跨中间的区间， 接着对半分，直到，左边与右边的值相等时退出这一层的递归，开始比较以及求和运算 查找到每一区间的最大和，然后比较三个区间的和找出最大的那一个。
步骤：1，首先读入，N和一系列数值存入数组 2，写递归出口，当左边的坐标和右坐标相等并且该值大于0时，return 此时的数组值，反之返回0 3，划分区域，找到中间坐标， 4，递归左边（调用自身改变下标即可）利用同样的方式，找到左边最大的和 4，递归右边（同上）利用同样的方式，找到右边最大的和 5，递归中间区间（从中间开始分别向左和向右找到一个和最大的序列（线性查找））， 左右两边的值相加。 6，比较这三个数，那个数最大，返回即可。 代码实现：
# include<iostream> # define Max 100010 using namespace std; //查找三个中的最大值 int cmp(int a, int b, int c) { // return a > b ? a > c ? a : c : b > c ? b : c; //cout << a << " " << b << " " << c << endl; if (a > b) { if (a > c) return a; else return c; } else { if (b > c) return b; else return c; } } int FindMax(int list[], int left, int right) { //出口 if (left == right) { if(list[left]>0) //只返回大于0 的值 return list[left]; else return 0; } int center = (left + right) / 2; //找到中间坐标 int MaxLeft = FindMax(list, left, center); //左边的最大值 int MaxRight = FindMax(list, center + 1, right); //右边的最大值 int MaxLeftMinde = 0; int ThisLeftMinde = 0; //从中间向左边遍历 for (int i = center; i >= left; i--) { ThisLeftMinde += list[i]; if (MaxLeftMinde < ThisLeftMinde) { MaxLeftMinde = ThisLeftMinde; } } int ThisRightMinde = 0; int MaxRightMinde = 0; //从中间向右边遍历 for (int i = center+1; i <= right; i++) { ThisRightMinde += list[i]; if (MaxRightMinde < ThisRightMinde) { MaxRightMinde = ThisRightMinde; } } int MaxMinde = MaxLeftMinde + MaxRightMinde; //cmp(MaxMinde, MaxRight, MaxLeft); return cmp(MaxMinde, MaxRight, MaxLeft); } int main() { //读入该序列长度 int n; cin >> n; //定义一个数组存放该序列 int a[Max]; for (int i = 0; i < n; i++) { cin >> a[i]; } cout << FindMax(a, 0, n - 1); }总结：分而治之，把问题由大化小，分开处理后，再结合起来，将该问题，划分成找左边，找右边，以及找包含中间的最大值，找到之后，合起来比较大小取最大的，这就是递归一层做的事。找到最左边的一个值开始向上做（左边右边值的个数不断扩大）求和运算。
