文章目录

1. 1. 最大子序列问题
   1. 1.1. 问题描述：
   2. 1.2. 算法1
   3. 1.3. 算法2
   4. 1.4. 算法3
   5. 1.5. 算法4
   6. 1.6. 参考

最大子序列问题

问题描述：

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

算法1

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

public static int getMaxSubVector1(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)

public static int getMaxSubVector2(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)

public static int getMaxSubVector4(int[] b,int l,int u){  
          
        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));  
    }  
    public static  int max3(int x,int y,int z){  
        if(x<y){  
            x=y;  
        }  
        if(x>z){  
            return x;  
        }  
        return z;  
}

算法4

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

public static int getMaxSubVector5(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;  
}

参考

以上算法思想参考《编程珠玑》第二版