编程珠玑第八章-算法设计技术

首先思考一个问题，给定一个含有n个元素的vector，找出其中最大的子向量（即所有元素之和为最大值）。如果是都为正数，那么问题变得十分简单，整个vector即是最大子向量，但是如果是正数负数混合的形式呢？问题将变得复杂，接下来将简要介绍几种算法的思路。其复杂度由最初的立方算法降低到最终的线性算法!(提供的代码细节处如数据类型例如int之类自己根据情况填加)
立方算法，思想很简单，即遍历所有情况：

maxfactor = 0;
for (i = 0；i<n; i++)
{
    for(j = i; j < n ; j++)
        sum = 0;
        for(k = i; k < j ; k++)
            sum += x[k];
        maxfactor = max(maxfactor,sum);//此处采用字符？：的形式更好
} 

其实不必每有一个[i,j]便重新求和一次，可以在遍历的过程中进行求和，因此，可以降低算法的复杂度为平方算法：

maxfactor = 0;
for (i = 0；i<n; i++)
{
    sum = 0;
    for(j = i; j < n ; j++)     
        sum += x[j];
        maxfactor = max(maxfactor,sum);
} 

使用常见的分治算法又可以进一步的降低算法的复杂度O(nlogn)：

float maxsum(1,u)
{
    if 1 > u
        return -1;
    if 1 == u
        return max(0,u);
    return m = (1 + u)>>1;
    //the left
    leftmax = sum = 0;
    for(i = m ; i > 1 ; i--)
    {
        sum += x[i];
        leftmax = max(leftmax,sum);
    }
    //the right
    rightmax = sum = 0;
    for(i = m ; i < n ; i++)
    {
        sum += x[i];
        rightmax = max(rightmax,sum);
    }
    return max(leftmax+rightmax,maxsum(1,m),max(m+1,n));

}

扫描算法，思路借鉴分治算法，不过使复杂度达到最低O(n)，即线性算法：

maxfactor = 0;
maxending = 0;
for (i = 0; i < n; i++)
{
    maxending += x[i];
    maxending = max(maxending,0);
    maxfactor = max(maxfactor,maxending);
}

注意：复杂度低的算法不意味着对于任何规模的问题，运行时间都低于复杂度高的算法，若通过画制时间曲线，会发现有一个拐点，在拐点处相等，规模越大，低复杂度算法的优势越明显。