算法优化例子

最大连续子序列和问题：给定（可能是负的）整数序列，寻找（并标识）的值为最大的序列。如果所有的整数都是负的，那么最大连续子序列的和是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次的循环，所以是一个线性算法。

总结

算法效率提升有两种，一是程序上的优化，一是设计思想上的优化。思想上的优化是本质上的改变。