文章目录
  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):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)

1
2
3
4
5
6
7
8
9
10
11
12
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)

1
2
3
4
5
6
7
8
9
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;
}

参考

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

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