问题描述：有这样一个序列：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; } 注：以上算法思想参考《编程珠玑》第二版