如何求出最大子数组之和

野性酷女 2023-07-04 12:46 18阅读 0赞

问题描述：一个有n个元素的数组，元素中有正有负，数组中**一个或者连续多个元素可以组成一个子数组**，求子数组中和最大的？

##### 方法一：暴力法 #####

> 三层循环，找出所有的子数组，并求出他们对应的和，再取最大值。

代码如下：

package Array;
    
    public class MaxSubArray {
             //求最大子数组之和
    	public static int maxSubArray(int array[]) {
        
    		int  len  = array.length;
    		int ThisSum = 0,MaxSum = 0,i,j,k;
    		for(i=0;i<len;i++)
    			for(j=i;j<len;j++) {
        
    				ThisSum = 0;
    				for(k=i;k<j;k++)
    					ThisSum += array[k];
    				if(ThisSum>MaxSum)
    					MaxSum = ThisSum;
    			}
    		return MaxSum;
    				
    	}
    	
    	public static void main(String[] args) {
        
    		int array[] = {
        1,-4,7,-5,2,6};
    		System.out.println("最大子数和为："+maxSubArray(array));
    	}
    
    }

运行截图：  
![在这里插入图片描述][20200211102154915.png]

##### 方法二：重复利用已计算的的子数组和 #####

> 例如：Sum\[ i , j \] = Sum \[ i , j - 1 \] + arr\[ j \] ，采用这种方式可以省去计算 Sum \[ i , j - 1 \] 的时间。

代码如下：

package Array;
    
    public class MaxSubArray2 {
            
    	public static int maxSubArray(int array[]) {
        
    		int len = array.length;
    		int maxSum = Integer.MIN_VALUE;
    		for(int i=0;i<len;i++) {
        
    			int sum = 0;
    			for(int j=i;j<len;j++) {
        
    				sum += array[j];
    				if(sum>maxSum) {
        
    					maxSum = sum;
    				}
    			}
    		}
    		return maxSum;
    	}
    	
    	public static void main(String[] args) {
        
    		int array[] = {
        1,-4,7,-5,2,6};
    		System.out.println("最大子数组之和："+maxSubArray(array));
    	}
    
    }

运行截图：  
![在这里插入图片描述][20200211095819414.png]

##### 方法三：动态规划法 #####

> 根据数组的最后一个元素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 Array;
    
    public class MaxSubArray3 {
        
    	public static int max(int m,int n ) {
        
    		return m>n ? m:n;
    	}
    	public static int maxSubArray(int array[]) {
        
    		int n = array.length;
    		int End[] = new int[n];
    		int All[] = new int[n];
    		End[n-1] = array[n-1];
    		All[n-1] = array[n-1];
    		End[0] = All[0] = array[0];
    		for(int i = 1;i<n;i++) {
        
    			End[i] = max(End[i-1]+array[i],array[i]);
    			All[i] = max(End[i],All[i-1]); 
    		}
    		return All[n-1];
    	}
    	public static void main(String[] args) {
        
    		int array[] = {
        1,-4,7,-5,2,6};
    		System.out.println("最大子数组和："+maxSubArray(array));
    	}
    
    }

运行截图：  
![在这里插入图片描述][20200211102053626.png]

[20200211102154915.png]: https://img-blog.csdnimg.cn/20200211102154915.png
[20200211095819414.png]: https://img-blog.csdnimg.cn/20200211095819414.png
[20200211102053626.png]: https://img-blog.csdnimg.cn/20200211102053626.png