转载

最大子序列问题

问题描述：

有这样一个序列：23,-23,11,43,-45,29,34,0,23,-12 ，求出这个序列中的最大子序列的和，例如从第0个元素到第3个元素是一个子序列，其和为54，最短的子序列可以只有一个元素，最长的子序列可以包含所有元素。

算法1

也是我们第一个想到的算法，是非常容易理解的一个算法，但是它效率最低，平均时间复杂度为O(n^3):

publicstaticintgetMaxSubVector1(int[] m){  
    int maxSubVector=0;  
    int i,j=0,k=0;  
    for(i=0;i<m.length;i++){  
        for(j=i;j<m.length;j++){  
            int sum=0;  
            for( k=i;k<j;k++){  
                sum+=m[k];  
                maxSubVector=Math.max(maxSubVector,sum);  
            }     
        }     
    }  
    return maxSubVector;  
}

算法2

这是一个稍微改进的算法，它的平均时间复杂度为O(n^2)

publicstaticintgetMaxSubVector2(int[] m){  
    int maxSubVector=0;  
    int i,j=0;  
    for(i=0;i<m.length;i++){  
        int sum=0;  
        for(j=i;j<m.length;j++){  
            sum+=m[j];  
            maxSubVector=Math.max(maxSubVector, sum);  
        }  
    }  
    return maxSubVector;  
}

算法3

我们可以用分治算法的思想来解决这个问题，这样可以将平均时间复杂度降到O(nlogn)

publicstaticintgetMaxSubVector4(int[] b,intl,intu){  
          
        int sum=0;  
        int m = (l+u)/2;  
        if(l>u) return 0;  
        if(l==u) return Math.max(0,b[1]);  
        int lmax=sum=0;  
        for(int i=m;i>=1;i--){  
            sum+=b[i];  
            lmax=Math.max(lmax, sum);  
        }  
        int rmax=sum=0;  
        for(int i=u;i>m;i--){  
            sum+=b[i];  
            rmax=Math.max(rmax, sum);     
        }  
        return max3(lmax+rmax, getMaxSubVector4(b,l,m),getMaxSubVector4(b,m+1,u));  
    }  
    publicstaticintmax3(intx,inty,intz){  
        if(x<y){  
            x=y;  
        }  
        if(x>z){  
            return x;  
        }  
        return z;  
}

算法4

这个算法是一种扫描的思想，是一种线性时间O(n)

publicstaticintgetMaxSubVector5(int[] b){  
    int maxSubVector=0;  
    int maxEnding=0;  
    for(int i=0;i<b.length;i++){  
        maxEnding=Math.max(maxEnding+b[i], 0);  
        maxSubVector=Math.max(maxSubVector, maxEnding);  
    }  
    return maxSubVector;  
}