如何求数组连续最大和(四种方法)

it2023-10-08  78

  一个有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) { // TODO Auto-generated method stub 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) { // TODO Auto-generated method stub 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) { // TODO Auto-generated method stub 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) { // TODO Auto-generated method stub 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) { // TODO Auto-generated method stub 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()); } }

运行结果:

最新回复(0)