求最大子数组之和的方法解析（2种可选）
问题描述：一个有n个元素的数组，这n个元素可以是正数也可以是负数，求最大子数组的和。
方法1：蛮力法
思路：最简单也是最容易想到的方法就是找出所有子数组，然后求所有子数组的和，在所有子数组的和中取最大值。
/**
*方法1（蛮力法）：两次循环求最大子数组之和
*/
publicstaticintmaxSubArray1(int[]a){
inti,j;
intThisSum=0;
intMaxSum=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;
}
}
}
returnMaxSum;
}
方法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和自身之前谁更大
*/
publicstaticintmax(intm,intn){
returnm>n?m:n;
}
publicstaticintmaxSubArray2(int[]a){
intnAll=a[0];//有n个数字数组的最大子数组之和
intnEnd=a[0];//有n个数字数组包含最后一个元素的子数组的最大和
for(inti=1;i<a.length;i++){
nEnd=max(nEnd+a[i],a[i]);
nAll=max(nEnd,nAll);
}
returnnAll;
}
privatestaticintbegin=0;
privatestaticintend=0;
/**
*求出最大子数组的开始begin，结尾end，以及整个子数组
*/
publicstaticintmaxSubArray3(int[]a){
intmaxSum=Integer.MIN_VALUE;
intnSum=0;
intnStart=0;
for(inti=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;
}
}
returnmaxSum;
}
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持毛票票！