求最大子数组之和的方法解析(2种可选)

时间:2021-12-27 04:19:06

问题描述:一个有n个元素的数组,这n个元素可以是正数也可以是负数,求最大子数组的和。

方法1:蛮力法

思路:最简单也是最容易想到的方法就是找出所有子数组,然后求所有子数组的和,在所有子数组的和中取最大值。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
  * 方法1(蛮力法):两次循环求最大子数组之和
  */
 public static int maxSubArray1(int[] a){
  int i,j;
  int ThisSum=0;
  int MaxSum=0;
  for (i = 0; i < a.length; i++) {
   ThisSum=a[i];
   for(j=i+1;j<a.length;j++){
    ThisSum+=a[j];
    if(ThisSum>MaxSum){
     MaxSum=ThisSum;
    }
   }
  }
  return MaxSum;
 }

方法2:优化的动态规划

思路:首先可以根据数组的最后一个元素a[n-1]与最大子数组的关系分为以下三种情况:

1) 最大子数组包含a[n-1],即以a[n-1]结尾。

2) a[n-1]单独构成最大子数组。

3) 最大子数组不包含a[n-1],那么求a[1,...,n-1]的最大子数组可以转换为求a[1,...,n-2]的最大子数组。

通过上述分析可以得出如下结论:假设已经计算出(a[0],...a[i-1])最大的一段数组和为All[i-1],同时也计算出(a[0],...a[i-1])中包含a[i-1]的最大的一段数组和为End[i-1],

则可以得出如下关系:All[i-1]=max{a[i-1],End[i-1],All[i-1]}。利用这个公式和动态规划的思想解决问题。(代码中还解决了起始位置,终止位置的问题)

?
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
  * 方法2:优化的动态规划方法
  * nEnd就是通过“数组依次相加加到a[i],然后与a[i]做比较”得来的,保存较大的。因为如果前面的数加到a[i]
  * 还没有a[i]本身大,那么前面的数也就对最大子数组和没有贡献。厉害
  * nAll就是记录一下之前的新得到的nEnd和自身之前谁更大
  */
 public static int max(int m,int n){
  return m>n?m:n;
 }
 public static int maxSubArray2(int[] a){
  int nAll=a[0];//有n个数字数组的最大子数组之和
  int nEnd=a[0];//有n个数字数组包含最后一个元素的子数组的最大和
  for (int i = 1; i < a.length; i++) {
   nEnd=max(nEnd+a[i],a[i]);
   nAll=max(nEnd, nAll);
  }
  return nAll;
 }
 private static int begin=0;
 private static int end=0;
 /**
  * 求出最大子数组的开始begin,结尾end,以及整个子数组
  */
 public static int maxSubArray3(int[] a){
  int maxSum=Integer.MIN_VALUE;
  int nSum=0;
  int nStart=0;
  for (int i = 0; i < a.length; i++) {
   if(nSum<0){
    nSum=a[i];
    nStart=i;
   }
   else{
    nSum+=a[i];
   }
   if(nSum>maxSum){
    maxSum=nSum;
    begin=nStart;
    end=i;
   }
  }
  return maxSum;
 }

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持服务器之家!

原文链接:http://www.cnblogs.com/winorgohome/p/6038320.html