最大连续子序列问题求解方法总结 转载

1.最原始，最古老，最暴力的方法。。。
        best = a[1];
        for(i = 1; i <= n; i++)
        {
                int sum = 0;
                for(j = i; j <= n; j++)
                {
                        sum += a[j];
                        if(sum > best)
                                best = sum;
                }
        }
时间复杂度是T(n) = O(n^2)

2.第一次优化：利用“连续子序列之和等于两个前缀和之差”
        best = s[1];  //引入的s数组中存放的是前缀和
        for(int i = 1; i <= n; i++)
                for(int j = i; j<= n; j++)
                {
                        best = (best > (s[j] - s[i])? best : (s[j] - s[i]));   //更新最大值
                }
时间复杂度为：T(n) = O(n^2)

3.再次优化：分治法
int maxsum(int *a, int x, int y)
{
        int i, m, v, L, R, max;
        if(y-x == 1)
                return a[x];
        m = x + (y-x)/2;
        max = maxsum(a, x, m) > maxsum(a, m, y) ? maxsum(a, x, m) : maxsum(a, m, y);
        v = 0;
        L = a[m-1];
        for(int i = m-1; i >= x; i--)
        {
                v += a[i];
                L = L > v? L: v;
        }
        v = 0;
        R = a[m];
        for(int i = m; i < y; i++)
        {
                v += a[i];
                R = R > v? R: v;
        }
        return max > (L+R)? max: (L+R);
}
时间复杂度： T(n) = O(n*logn)

4.继续优化
DP, 联机算法：
        sum = a[1], temp = a[1];
        for(int i = 2; i <= n; i++)
        {
                if(sum > 0)
                        temp += a[i];
                else
                        temp = a[i];
                if(temp > sum)
                        sum = temp;
        }
时间复杂度： T(n) = O(n)

附：
如果在任何时刻，算法都能对它已经读入的数据给出子序列问题的正确答案，具有这种特性的算法叫做联机算法。仅需要常量空间并以线形时间运行的联机算法几乎是完美的算法。
一个经典的问题：求最大子序列和的算法就是这样一个完美的算法