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

下面是解决这个问题的算法(Java语言实现)：

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

public static int getMaxSubVector1(int[] m){

int maxSubVector=0;

int i,j=0,k=0;

for(i=0;i

for(j=i;j

int sum=0;

for( k=i;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

int sum=0;

for(j=i;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

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

maxEnding=Math.max(maxEnding+b[i], 0);

maxSubVector=Math.max(maxSubVector, maxEnding);

}

return maxSubVector;

}

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