求最大子数组之和的方法解析(2种可选)
程序员文章站
2024-03-11 10:32:25
问题描述:一个有n个元素的数组,这n个元素可以是正数也可以是负数,求最大子数组的和。
方法1:蛮力法
思路:最简单也是最容易想到的方法就是找出所有子数组,然后求所有子数...
问题描述:一个有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<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]}。利用这个公式和动态规划的思想解决问题。(代码中还解决了起始位置,终止位置的问题)
/** * 方法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; }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持!