首页 > 代码库 > 第四章 分治策略 4.1 最大子数组问题 (减治法,别人的,拿来看看)
第四章 分治策略 4.1 最大子数组问题 (减治法,别人的,拿来看看)
/** * 获得连续子数组的最大和 * * @author dfeng * */ private static long getMax(long a, long b) { return a > b ? a : b; } /** * 获得连续子数组的最大和 * * @param array * @return 最大和,此处用了Long型是为了表示当参数为null或空时,可以返回null,返回其它任何数字都可能引起歧义。 */ public static Long getMax(int[] array) { if (array == null || array.length <= 0) { return null; } long maxSum = array[0]; // 所有子数组中最大的和 long righteEdge = array[0]; // 右侧子数组的最大和 for (int i = 1; i < array.length; i++) { // 当右侧子数组的最大和为负数时,对于新数组,右侧子数组的最大和为新增加的数。 if (righteEdge < 0) { righteEdge = array[i]; } else { // 为正数时,对于新数组,右侧子数组的最大和为新增加的数 + 原来的最大和。 righteEdge += array[i]; } // 所有子数组中最大的和 maxSum = getMax(righteEdge, maxSum); } return maxSum; } public static void main(String[] args) { int[] array = { -111, -2, -3, -10, -4, -7, -2, -5 }; System.out.println("Max sum: " + getMax(array)); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。