最大连续子序列和问题：给定（可能是负的）整数序列，寻找（并标识）
的值为最大的序列。如果所有的整数都是负的，那么最大连续子序列的和是0。
1、典型的)
算法
最简单的算法是直接的穷尽查找，即蛮力算法(Brute Force Algorithm)，找出所有子序列并求和，遍历所有求和结果找出最大值。
int maxSubsequenceSum(int a[], int &start, int &end){
int size = sizeof(a)/sizeof(a[0]);
int maxSum = 0;
// 起始位置遍历
for (int i=0; i<size; i++){
// 结束位置遍历
for (int j=i; j<size; j++){
int thisSum = 0;
// 子序列求和
for (int k=i; k<=j; k++){
thisSum += a[k];
if (thisSum>maxSum){
maxSum = thisSum;
start = i;
end = j;
}
}
}
}
return maxSum;
}
这一算法非常简单易于理解，最外层循环需要执行n次，第二层循环需要执行n-i次，第三层循环执行j-i次，由此可得时间复杂度为，即
。
在该算法中嵌套循环几乎贡献了所有的时间复杂度，简单的理解一个循环有N的时间复杂度，那么三层嵌套就是N的三次方。
2、改进的)
算法
由蛮力算法可知，导致时间复杂度的主要是循环，通过减少循环就可以降低时间复杂度。分析蛮力算法可得，第三层循环计算thisSum有太多的重复步骤，没必要每次都重新求和，利用在第二层循环累加即可。
int maxSubsequenceSum(int a[], int &start, int &end){
int size = sizeof(a)/sizeof(a[0]);
int maxSum = 0;
for (int i=0; i<size; i++){
int thisSum = 0;
for (int j=i; j<size; j++){
thisSum += a[j];
if (thisSum>maxSum){
maxSum = thisSum;
start = i;
end = j;
}
}
}
return maxSum;
}
由于循环只有两层，所以时间复杂度降低为。
3、线性算法
从平方算法降低到线性算法还需要再删除一个循环，但是平方算法降低到线性算法，不能只是简单的改变程序，需要思想。前两种算法本质上还是穷尽法，只不过有一些巧妙的改进，想要得到线性算法就需要改变思想。
可以通过分析来排除一些可能的子序列。如果一个子序列是负的，那么它绝对不会出现在最大连续子序列的开始部分，这非常容易理解，因为如果开始部分是负的，显然起到减小作用，为什么又要包含进去呢？以某一序列{a, b, c, d, e, f, g, h, i, j, k......y, z}为例，如果a是负的，肯定不会以a开头；如果cdef是负的，可以直接跳到g开始，可能会问为什么不从d开始呢？原因在于c肯定不会是负的，见a情况，那么整个是负的，c又是正的，那么def也肯定是负的，没有必要再考虑了。
int maxSubsequenceSum(int a[], int &start, int &end){
int size = sizeof(a)/sizeof(a[0]);
int maxSum = 0, thisSum = 0, start = 0;
for (int i=0; i<size; i++){
thisSum += a[i];
// 如果和为负，起点设为下一位
if (thisSum<0){
thisSum = 0;
start = i+1;
}
// 如果大于最大值，终点设为此位
if (thisSum>maxSum){
maxSum = thisSum;
end = i;
}
}
return maxSum;
}
由于只用到一个至多循环n次的循环，所以是一个线性算法。
总结
算法效率提升有两种，一是程序上的优化，一是设计思想上的优化。思想上的优化是本质上的改变。
