用分治法实现最大子数组问题（Java）

本文主要是介绍用分治法实现最大子数组问题（Java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

终于把这个搞出来了，中间出现了好多小问题，伪代码和算法思想可以参考算法导论。

package com.alibaba;public class MaxSubarray
{public static void main(String[] args){int[] array = { 1, -2, -3, 4, 5, 6, -3, 4, -11 };int[] result = MaxSubarray.findMaxSubarray(array, 0, array.length - 1);for (int i = 0; i < result.length; i++){System.out.println(result[i]);}}public static int[] findMaxCrossingSubarray(int[] array, int low, int mid, int high){int leftsum = Integer.MIN_VALUE;int sum1 = 0;int maxleft = 0;for (int i = mid; i >= 0; i--){sum1 = sum1 + array[i];if (sum1 > leftsum){leftsum = sum1;maxleft = i;}}int rightsum = Integer.MIN_VALUE;int sum2 = 0;int maxright = 0;for (int j = mid + 1; j <= high; j++){sum2 = +array[j];if (sum2 > rightsum){rightsum = s

这篇关于用分治法实现最大子数组问题（Java）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---