最大连续子序列求和

最大连续子序列求和

题目：

给你一个整数列，A₁, A₂, A₃, ⋯, A_n，在其中找到一个连续的子链A_i, A_i + 1, ⋯, A_j(1 ≤ i ≤ j ≤ N)使得$\sum_{k=i}^{j}A_k$的值最大，如果所有的数都是负数，则规定最大连续子链和为0

这个其实是非常简单的一道题，随着思维的深入，时间复杂度可以多次降低，比如说，我们肯定可以想到一个时间复杂度为O(N³)的算法：

int maxSubsequenceSum(int A[],int size,int &start,int &end){
    int result = 0;
    for(int i = 0;i < size; i++)
        for(int j = i;j < size; j++){
            int count = 0;
            for(int k = i;k <= j; k++)
                count += A[k];
            if(count > result){
                result = count;
                start = i;
                end = j;
            }
		}
    return result;
}

这个想法比较简单，我就不写注释了。简单分析一下，这里面其实有一个十分浪费的地方，就是每次都需要重新计算$\sum_{k=i}^{j}A_k$的值，这种做法实际上是没什么必要的，我们完全可以进行预处理，这样时间复杂度降到了O(N²)，这就是前缀和的方法：

int maxSubsequenceSum(int A[],int size,int &start,int &end){
    int result = 0;
    if(size == 1){
        start = 0;
        end = 0;
        return max(result, A[0]);//如果只有一个数，那么就不用想那么多，这个数是正数，就是这个正数，这个数是负数，就是0
    }
    int *sum = new int [size+1];
    sum[0] = A[0];
    for(int i = 1;i < size; i++)
        sum[i] = sum[i-1] + A[i];//前缀和，即sum[i]就是A[0]+A[1]+...+A[i]的值
    for(int i = 0;i < size; i++)
        for(int j = i;j < size; j++){
            if(result <= (sum[j] - sum[i])){
                start = i;
                end = j;
                result = (sum[j] - sum[i]);//这样，我们只需要用sum[j] - sum[i]就可以表示从i到j中所有元素的和
            } 
		}
    return result;
}

笔者这边申明一下，如果返回结果是0，那就不需要再打出来start和end的值了。具体实现可以写在主函数里，笔者这里就不再赘述了。还有就是sum[j]-sum[i]到底需不需要加括号，这个关于C++运算符号优先级的问题，笔者打算后面专门开一篇来介绍。

可能有人会对我说：

主播主播，你的方法确实很强，但是还是太吃时间复杂度了，有没有更简便的方法推荐呢？

有的兄弟有的

（理解一下笔者的精神状态）

好了，正经点，其实还有一种O(n)的方法：

int maxSubsequenceSum(int A[],int size,int &start,int &end){
    int i = 0, result = 0, count = 0;
    start = 0;//把起点都初始化一下
    for(int j = 0; j < size; j++){//j往后移，计算这时候的子链和
        count += A[j];
        if(count > result){//如果当下子链和比我之前的结果大，那么就将结果替换为当下的子链和
            result = count;
            start = i;
            end = j;
		}
        else if(count < 0){//重点：如果我当下的子链和是小于零的，那么这一段我直接抛掉，将我计算的起始点放到j+1的位置
            count = 0;
            i = j + 1;
		}
	}
    return result;
}

对于这个方法，我写了一些备注，不过可能还是有读者没有看懂，我仔细来说一下：i是起点，是我当下计算子列的起始点，然后我去用j来遍历A[]这个数组，将j的结果累计到count中，每一次循环中，对count进行一次检查，如果count小于0，那么直接将i设为j+1，而count归零。

为什么这样做是正确的？因为任何一个子数列加上一个和小于0的子数列都会使合成的总数列和变小，那么既然如此，我就不计入和小于0的子数列，这一段，在我眼中，属于“亏本”的状态，不管它前置还是后置，我们都不会加上它，简单来说，就是如果一段连续数列的和是负数，它就不会是最大子序列的开头。

如果从数学上理解了这点，这道题就迎刃而解了。