問題描述：有這樣一個序列：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<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;
}
注：以上算法思想參考《編程珠玑》第二版
