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

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

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

方法1：蛮力法

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

/**

* 方法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

ThisSum+=a[j];

if(ThisSum>MaxSum){

MaxSum=Thttp://hisSum;

}

}

}

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]}。利用这个公式和动态规划的思想解决问题。(代码中还解决了起始位置，终止位置的问题)

/**

* 方法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，以及整个子数组

*/

http:// 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;

}

ThisSum+=a[j];

if(ThisSum>MaxSum){

MaxSum=Thttp://hisSum;

}

}

}

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]}。利用这个公式和动态规划的思想解决问题。(代码中还解决了起始位置，终止位置的问题)

/**

* 方法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，以及整个子数组

*/

http:// 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;

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。