最大连续子列和问题
Q： 给定N个整数的序列{A_1,A_2, …, A_N}，求函数 f(i,j)=max{0, \sum_{k=i}^{j}{A_k}}
A1：暴力解法。遍历计算全部子列和，然后从中再去寻找最大的那一个。
int maxSubseqSum(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++ )
thisSum += A[k];
if( thisSum > maxSum ) // 如果刚得到的这个子列和更大
maxSum = thisSum; // 则更新结果
}
}
return maxSum;
}
时间复杂度：T(N) = O(N^3)
A2：对A1的改进。A1的方法很笨，但是笨在哪里呢？其在j循环内层，每次对thisSum进行归零，然后再从头进行累加操作；但实际上，对于相同的i，不同的j的情况，我们只需要不停维护thisSum的值，使其和maxSum做比较即可，而完全不用每次都从最顶端加起。
也就是说，k循环是完全没有必要的。
int maxSubseqSum(int A[], int N){
int thisSum, maxSum = 0;
int i, j, k;
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，只要继续维护thisSum的值即可
if( thisSum > maxSum ) // 如果刚得到的这个子列和更大
maxSum = thisSum; // 则更新结果
}
}
return maxSum;
}
时间复杂度：T(N) = O(N^2)
A3：分治思想。尽管 O(N^2) 已经比 O(N^3) 提高了一个量级，但是 O(N^2) 的算法效率仍然比较低下。当实现了一个O(N^2)的算法时，本能的应该去思考，如何将其优化为O(NlogN)的算法。
在本题中，可以考虑使用分治思想，对整个数组进行取半，然后依次递归求解，从而实现O(NlogN)的时间复杂度。需要注意的是，本题中简单的分而治之不能囊括全部情况，还需要考虑跨越算法二分边界的子列和。
int maxSubseqSum(int arr[], int l, int r){
if(l == r) return arr[l] > 0 ? arr[l] : 0; // 递归到底，返回正整数结果，否则返回0
int mid = (l + r) / 2; // 取中间值，分
int maxLeft = getMaxNum(arr, l, mid); // 分治的过程，递归求最大值
int maxRight = getMaxNum(arr, mid + 1, r);
int maxLeftSum = 0, tempLeftSum = 0; // merge的过程，计算跨越中间值的最大序列
for (int i = mid; i >= l; i--){ // 由中间向左侧扫描数组
tempLeftSum += arr[i]; // 依次累加求和
if (tempLeftSum > maxLeftSum) // 如果发现有连续的更大值，则记录下来
maxLeftSum = tempLeftSum;
}
int maxRightSum = 0, tempRightSum = 0;
for (int i = mid + 1; i <= r; i++){ // 由中间向右侧扫描数组
tempRightSum += arr[i]; // 依次累加求和
if (tempRightSum > maxRightSum){ // 如果有连续的更大值，记录下来
maxRightSum = tempRightSum;
}
// 在最后，对左侧最值，右侧最值，跨越中间值的最值求最大者，即为最大连续子列和
return Math.max(maxLeftSum + maxRightSum, Math.max(maxLeft, maxRight));
}
在这个分治的过程中，递归到底求最值没什么好解释的；重点在于merge的过程。
在具体进行merge时，由于是从中间值开始向两侧扫描的，且每逢更大值则记录下来，就可以保证最后maxLeftSum + maxRightSum的值为一个连续的子列和，也正是我们所需要的跨越中间值的最长子列。
因此，用该值与左侧最值，右侧最值求max，则能够得到我们想要的结果，也就是最大子列和。
时间复杂度： T(N) = 2 T(N/2) + cN，其中T(1)=O(1)
= 2 [2 T(N/2^2) + c N/2] + cN
= 2^kO(1) + c k N 其中 N/2^k=1
= O(N log N)
A4：在线处理算法，线性算法
在线的意思是指，每输入一个数据就进行即时处理，在任何一个地方终止输入，算法都能正确给出当前的解。
int maxSubseqSum(int A[], int N){
int thisSum, maxSum = 0;
int i;
for( i = 0; i < N; i++ ){
thisSum += A[i]; // 遍历整个数组，依次向右累加
if( thisSum > maxSum )
maxSum = thisSum; // 发现更大和，则更新当前结果
else if(thisSum < 0) // 如果当前子列和为负
thisSum = 0; // 则不可能使后面的部分和更大，抛弃之
}
return maxSum;
}
时间复杂度：T(N) = O(N)
这是能够想到的效率最高的算法了，因为再怎么说，也需要把整个数组扫描一遍才能得到结果。在线处理算法由于其即时处理的性质，保证了其可怕的效率。
