一个有n个元素的数组,则n个元素既可以是正数也可以是负数,数组中连续的一个或多个元素可以组成一个连续的子数组,一个数组可能有多个这种连续的子数组,求子数组和的最大值。 分析:
方法一:蛮力法
最简单的也是最容易的方法就是找出所有的子数组,然后求出数组的和,在所有子数组的和中取最大值。
实现代码:
package lock
;
public class T5
{
public static int maxSubArray(int[] arr
)
{
if(arr
==null
||arr
.length
<=1)
{
System
.out
.println("输入参数不合理!");
return -1;
}
int ThisSum
=0,MaxSum
=0,i
,j
,k
;
for(i
=0;i
<arr
.length
;i
++)
{
for(j
=i
;j
<arr
.length
;j
++)
{
ThisSum
=0;
for(k
=i
;k
<j
;k
++)
ThisSum
+=arr
[k
];
if(ThisSum
>MaxSum
)
MaxSum
=ThisSum
;
}
}
return MaxSum
;
}
public static void main(String
[] arg
) {
int arr
[]= {1,-2,4,8,-4,7,-1,-5};
System
.out
.println("连续最大的和为:"+maxSubArray(arr
));
}
}
运行结果:
算法性能分析:
这种算法的时间复杂度为O(N^ 3),显然效率太低,通过这种算法进行分析发现,许多子数组都重复计算了。
方法二:重复利用已经计算的子数组和
由于Sum[i,j]=Sum[i,j-1]+arr[j],在计算Sum[i,j]时可以使用前面已经计算出的Sum[i,j-1]而不需要重新计算,采用这种方法可以省去Sum[I,j-1]的时间,因此可以提高程序的效率,节省运算时间。
实现代码如下:
package lock
;
public class T6 {
public static int maxSubArray(int[] arr
)
{
if(arr
==null
||arr
.length
<=1)
{
System
.out
.println("输入参数不合理!");
return -1;
}
int maxSum
=Integer
.MIN_VALUE
;
for(int i
=0;i
<arr
.length
;i
++)
{
int sum
=0;
for(int j
=i
;j
<arr
.length
;j
++)
{
sum
+=arr
[i
];
if(sum
>maxSum
)
{
maxSum
=sum
;
}
}
}
return maxSum
;
}
public static void main(String
[] args
) {
int arr
[]= {1,-2,4,8,-4,7,-1,-5};
System
.out
.println("连续最大的和为:"+maxSubArray(arr
));
}
}
实验结果:
算法性能分析:
这种方法是用来双重循环,因此,时间复杂度为O(N^ 2)。
方法三:动态规划方法
可以采用动态规划的方法来降低算法的时间复杂度。 首先可以根据数组的最后一个元素arr[n-1]与最大子数组的关系分为以下三种情况讨论: 1)最大数组包含arr[n-1],即最大数组以arr[n-1]结尾。 2)arr[n-1]单独构成最大数组。 3)最大数组不包括arr[n-1],那么arr[1…n-1]的最大子数组可以转化为arr[1…n-2]的最大子数组。
实现代码:
package lock
;
public class T7 {
public static int maxSubArray(int[] arr
)
{
if(arr
==null
||arr
.length
<=1)
{
System
.out
.println("输入参数不合理!");
return -1;
}
int n
=arr
.length
;
int[]End
=new int[n
];
int[]All
=new int[n
];
End
[n
-1]=arr
[n
-1];
All
[n
-1]=arr
[n
-1];
End
[0]=All
[0]=arr
[0];
for(int i
=1;i
<n
;++i
)
{
End
[i
]=Integer
.max(End
[i
-1]+arr
[i
], arr
[i
]);
All
[i
]=Integer
.max(End
[i
],All
[i
-1]);
}
return All
[n
-1];
}
public static void main(String
[] args
) {
int arr
[]= {1,-2,4,8,-4,7,-1,-5};
System
.out
.println("连续最大的和为:"+maxSubArray(arr
));
}
}
实验结果:
算法性能分析:
与前面两种方法相比,这种方法的时间复杂度为O(N),显然效率更高,但是由于在计算的过程中额外申请了两个数组,因此该方法的空间复杂度也为O(N)。
方法四:优化的动态规划方法
可以定义两个变量来保存End[i-1]与All[i-1],并且可以重复利用。
实现代码:
package lock
;
public class T8 {
public static int maxSubArray(int[] arr
)
{
if(arr
==null
||arr
.length
<=1)
{
System
.out
.println("输入参数不合理!");
return -1;
}
int nAll
=arr
[0];
int nEnd
=arr
[0];
for(int i
=1;i
<arr
.length
;++i
)
{
nEnd
=Integer
.max(nEnd
+arr
[i
],arr
[i
]);
nAll
=Integer
.max(nEnd
,nAll
);
}
return nAll
;
}
public static void main(String
[] args
) {
int arr
[]= {1,-2,4,8,-4,7,-1,-5};
System
.out
.println("连续最大的和为:"+maxSubArray(arr
));
}
}
运行结果:
算法性能分析:
这种方法在保证了时间复杂度为O(N)的基础上,把算法的空间复杂度也降到O(1)。
引申:
在知道子数组最大值后,如何才能确定最大子数组的位置
分析:
为了得到最大子数组的位置,首先介绍另外一种最大子数组和的方法。通过公式End[i]=max(End[i-1]+arr{i},arr[i])的分析可以看出,当End[i-1]<0时,End[i]=array[i],其中End[i]表示包含array[i]的数组和,如果某一个值使得End[i-1]<0,那么就从arr[i]重新开始。可以利用这个性质非常容易地确定最大子数组的位置。
实现代码:
package lock
;
public class T9 {
private int begin
=0;
private int end
=0;
public int maxSubArray(int[] arr
){
int n
=arr
.length
;
int maxSum
=Integer
.MIN_VALUE
;
int nSum
=0;
int nStart
=0;
for(int i
=0;i
<n
;i
++) {
if(nSum
<0)
{
nSum
=arr
[i
];
nStart
=i
;
}else {
nSum
+=arr
[i
];
}
if(nSum
>maxSum
) {
maxSum
=nSum
;
begin
=nStart
;
end
=i
;
}
}
return maxSum
;
}
public int getBegin() {return this.begin
;}
public int getEnd() {return this.end
;}
public static void main(String
[] args
) {
T9 t
=new T9();
int arr
[]= {1,-2,4,8,-4,7,-1,-5};
System
.out
.println("连续最大的和为:"+t
.maxSubArray(arr
));
System
.out
.println("最大和对应的数组起始与结束坐标分别为:"+t
.getBegin()+","+t
.getEnd());
}
}
运行结果: