本文主要是介绍用分治法实现最大子数组问题(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)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!