算法导论_最大子数组问题(分治策略)
package com.wzs;import java.util.Arrays;/** * 算法导论--page41 * * @author Administrator * */public class FindMaximumSubArray {public static void main(String[] args) {int[] arr = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };int length = arr.length;SubArray subArray = findMaximumSubArray(arr, 0, length - 1);System.out.println("原数组为：" + Arrays.toString(arr));System.out.print("最大子数组为：");for (int i = subArray.low; i <= subArray.high; i++) {System.out.print(arr[i] + " ");}System.out.println("\n最大子数组开始坐标：" + subArray.low + " 结束坐标：" + subArray.high + " 最大和：" + subArray.sum);}/** * 最大子数组问题--分治策略 * * @param arr * 需要求的数组 * @param low * 数组的开始坐标 * @param high * 数组的结束坐标 * @return 子数组的和 */static SubArray findMaximumSubArray(int[] arr, int low, int high) {if (low == high) {return new SubArray(low, high, arr[low]);} else {int mid = (low + high) / 2;SubArray subArrayLeft = findMaximumSubArray(arr, low, mid);SubArray subArrayRight = findMaximumSubArray(arr, mid + 1, high);SubArray subArrayCross = findMaxCrossingSubArray(arr, low, mid, high);if (subArrayLeft.sum > subArrayRight.sum && subArrayLeft.sum > subArrayCross.sum) {return subArrayLeft;} else if (subArrayRight.sum > subArrayLeft.sum && subArrayRight.sum > subArrayCross.sum) {return subArrayRight;} else {return subArrayCross;}}}/** * 求跨越子数组的最大值 * * @param arr * 需要求的数组 * @param low * 数组开始坐标 * @param mid * 数组中间坐标 * @param high * 数组结束坐标 * @return 子数组的和 */static SubArray findMaxCrossingSubArray(int[] arr, int low, int mid, int high) {int leftSum = 0;// 左边子数组的和int leftIndex = mid;// 左边数组最大时数组坐标int sum = 0;for (int i = mid; i > 0; i--) {sum += arr[i];if (sum > leftSum) {leftSum = sum;leftIndex = i;}}int rightSum = 0;// 右边边子数组的和int righIndex = mid + 1;// 右边数组最大时数组坐标sum = 0;for (int i = mid + 1; i < high; i++) {sum += arr[i];if (sum > rightSum) {rightSum = sum;righIndex = i;}}return new SubArray(leftIndex, righIndex, leftSum + rightSum);}}/** * 子数组的和 * * @author Administrator * */class SubArray {int low;// 子数组的开始坐标int high;// 子数组的结束坐标int sum;// 子数组的和public SubArray(int low, int high, int sum) {super();this.low = low;this.high = high;this.sum = sum;}}