分治算法之最长子段和问题(Java)

本文主要是介绍分治算法之最长子段和问题(Java)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、利用分治法的思想实现的算法如下：

public static int maxSegSum(int [] arr, int begin, int end){int sum = 0;if(begin == end){if(arr[begin] > 0){return arr[begin];}else{return 0;}}int middle = (begin + end) / 2;int leftSum = maxSegSum(arr, begin, middle);int rightSum = maxSegSum(arr, middle + 1, end);int left = 0;int s1 = 0;for(int i = middle; i >= 0; i--){left += arr[i];if(left > s1){s1 = left;}}int right = 0;int s2 = 0;for(int i = middle + 1; i <= end; i++){right += arr[i];if(right > s2){s2 = right;}}sum = s1 + s2;if(sum <= leftSum){sum = leftSum;}if(sum <= rightSum){sum = rightSum;}return sum;}

二、测试程序如下：

public class MaxSegSum {public static int [] arr = new int[]{-20,11,-4,13,-5,-2};public static void main(String[] args) {int sum = maxSegSum(arr, 0, 5);System.out.print("原始数组为:	");for(int i = 0; i < arr.length; i++){System.out.print(arr[i] + "	");}System.out.println();System.out.print("最长子段和:	" + sum);}
}

三、运行结果：

原始数组为:	-20	11	-4	13	-5	-2	
最长子段和:	20

这篇关于分治算法之最长子段和问题(Java)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---