算法之1 | 最大子数组问题

vlambda
2022-02-09

算法之1 | 最大子数组问题

问题描述：

一个n个元素的数组，其中有正数也有负数，求一个子数组，使其元素之和最大。

例如：数组{1，-2，4，8，-4，7，-1，-5}，最大和的子数组为{4，8，-4，7}，和为15。

算法一：“蛮力”法

枚举所有的子数组，求出和，找出和最大的子数组。代码如下：

import java.util.Scanner;
public class maxSubArray {
 public static int maxSubArrayMethodTwo(int arr[]){ int size =arr.length; int maxSum=Integer.MIN_VALUE; for(int i=0;i<size;i++){
 int sum=0; for(int j=i;j<size;j++){ sum+=arr[j]; if(sum>maxSum){ maxSum=sum; } } } return maxSum; }
 public static void main(String[] args) { Scanner sc=new Scanner(System.in); int number=Integer.parseInt(sc.next()); //number表示数组的长度 int[] num=new int[number];
 //对数组元素循环赋值 for(int i=0;i<number;i++){ num[i]=(int)sc.nextInt(); } System.out.println(maxSubArrayMethodTwo(num));
 }
}

以上算法的时间复杂度为O(n^2)。

程序运行结果：

输入：8 1 -2 4 8 -4 7 -1 -5

输出：15

算法二：动态规划法

采用动态规划法降低算法的时间复杂度，算法描述如下：

最大子数组包含arr[0]；
最大子数组为arr[0]；
最大子数组不包含arr[0]，问题转为求arr[1]至arr[n-1]的一个序列。

代码如下：

import java.util.Scanner;
public class maxSubArray {
 public static int max(int m,int n){ return m>n ? m :n; }
 public static int maxSubArrayMethodThree(int arr[]){ 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]=max(End[i-1]+arr[i],arr[i]); All[i]=max(End[i],All[i-1]); }
 return All[n-1]; } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int number=Integer.parseInt(sc.next()); //number表示数组的长度 int[] num=new int[number];
 //对数组元素循环赋值 for(int i=0;i<number;i++){ num[i]=(int)sc.nextInt(); } System.out.println(maxSubArrayMethodThree(num));
 }
}