问题：
使用D&C/Recursion的最大子数组
东门焕
我想用一个算法实现最大子数组问题，该算法表现为（n log n）：
查找最大相邻子数组，或数组中相邻元素的最大和。
假设：并非所有元素都是负数
我有一些工作的解决办法；问题在于重叠中心数组，而适当的索引表示重叠子问题，一些数组得到正确的答案，而另一些数组没有得到正确的答案。
只是为了比较&为了确保正确性，我实现了一个被称为Kadane算法的解决方案（我认为复杂度为Omega(n))。
这是Kandane的算法(http://en.wikipedia.org/wiki/maximum_subarray_problem):
public static void Kadane(int array[]) {
int max_ending_here = 0;
for (int i = 0; i < array.length; i++) {
max_ending_here = max_ending_here + array[i];
max_so_far = Math.max(max_so_far, max_ending_here);
}
System.out.println("Kadane(int array []): " + max_so_far);
}
我的递归实现，它使用分治来比较子数组的最大值，然后对具有最大值的子数组进行make递归调用，直到递归结束
public static void findMaxSubArray(int[] array, int lowIndex, int highIndex) {
int mid = 0;
int arrayLength = 0;
int maxEndingHere = 0;
if (array == null) {
throw new NullPointerException();
} else if
//base condition
(array.length < 2 || (highIndex==lowIndex)) {
maxLowIndex = lowIndex;
maxHighIndex = highIndex;
System.out.println("findMaxSubArray(int[] array, int lowIndex, int highIndex)");
System.out.println("global Max Range, low:" + maxLowIndex + " high: " + maxHighIndex);
System.out.println("global Max Sum:" + globalMaximum);
} else {
System.out.println();
int lowMidMax = 0;
int midHighMax = 0;
int centerMax = 0;
//array length is always the highest index +1
arrayLength = highIndex + 1;
//if even number of elements in array
if (array.length % 2 == 0) {
mid = arrayLength / 2;
System.out.println("low: " + lowIndex + " mid: " + mid);
for (int i = lowIndex; i < mid; i++) {
System.out.print(array[i] + ",");
}
//calculate maximum contigous array encountered so far in low to mid indexes
for (int i = lowIndex; i < mid; i++) {
maxEndingHere = maxEndingHere + array[i];
if (maxEndingHere < 0) {
maxEndingHere = 0;
}
if (globalMaximum < maxEndingHere) {
//new maximum found
globalMaximum = lowMidMax = maxEndingHere;
lowIndex = i;
}
}
//end low mid calc
for (int i = mid; i <= highIndex; i++) {
System.out.print(array[i] + ",");
}
System.out.println("mid: " + mid + " high: " + highIndex);
//calculate maximum contigous array encountered so far in mid to high indexes
for (int i = mid; i <= highIndex; i++) {
maxEndingHere = maxEndingHere + array[i];
if (maxEndingHere < 0) {
maxEndingHere = 0;
}
if (globalMaximum < maxEndingHere) {
//new maximum found
globalMaximum = midHighMax = maxEndingHere;
mid = i;
}
}
//end mid high calc
//calculate maximum contigous array encountered so far in center array
int lowCenter = mid -1;
int highCenter = highIndex -1;
System.out.println("lowCenter: " + lowCenter + " highCenter: " + highCenter);
for (int i = lowCenter; i < highCenter; i++) {
System.out.print(array[i] + ",");
}
//calculate maximum contigous array encountered so far in low to mid indexes
for (int i = lowCenter; i < highCenter; i++) {
maxEndingHere = maxEndingHere + array[i];
if (maxEndingHere < 0) {
maxEndingHere = 0;
}
if (globalMaximum < maxEndingHere) {
//new max found
globalMaximum = centerMax = maxEndingHere;
lowCenter = i;
}
}
//end center calc
//determine which range contains the maximum sub array
//if lowMidMax <= midHighMax and centerMax
if (lowMidMax >= midHighMax && lowMidMax >= centerMax) {
maxLowIndex = lowIndex;
maxHighIndex = mid;
//recursive call
findMaxSubArray(array, lowIndex, mid);
}
if (midHighMax >= lowMidMax && midHighMax >= centerMax) {
maxLowIndex = mid;
maxHighIndex = highIndex;
//recursive call
findMaxSubArray(array, mid, highIndex);
}
if (centerMax >= midHighMax && centerMax >= lowMidMax) {
maxLowIndex = lowCenter;
maxHighIndex = highCenter;
//recursive call
findMaxSubArray(array, lowCenter, highCenter);
}
}//end if even parent array
//else if uneven array
else {
mid = (int) Math.floor(arrayLength / 2);
System.out.println("low: " + lowIndex + " mid: " + mid);
for (int i = lowIndex; i < mid; i++) {
System.out.print(array[i] + ",");
}
//calculate maximum contigous array encountered so far in low to mid indexes
for (int i = lowIndex; i < mid; i++) {
maxEndingHere = maxEndingHere + array[i];
if (maxEndingHere < 0) {
maxEndingHere = 0;
}
if (globalMaximum < maxEndingHere) {
//new maximum found
globalMaximum = lowMidMax = maxEndingHere;
lowIndex = i;
}
}
//end low mid calc
System.out.println("mid+1: " + (mid + 1) + " high: " + highIndex);
for (int i = mid + 1; i <= highIndex; i++) {
System.out.print(array[i] + ",");
}
//calculate maximum contigous array encountered so far in mid to high indexes
for (int i = mid + 1; i <= highIndex; i++) {
maxEndingHere = maxEndingHere + array[i];
if (maxEndingHere < 0) {
maxEndingHere = 0;
}
if (globalMaximum < maxEndingHere) {
//new maximum found
globalMaximum = midHighMax = maxEndingHere;
mid = i;
}
}
//end mid high calc
//calculate maximum contigous array encountered so far in center array
int lowCenter = mid;
int highCenter = highIndex -1;
System.out.println("lowCenter: " + lowCenter + " highCenter: " + highCenter);
for (int i = lowCenter; i < highCenter; i++) {
System.out.print(array[i] + ",");
}
//calculate maximum contigous array encountered so far in low to mid indexes
for (int i = lowCenter; i < highCenter; i++) {
maxEndingHere = maxEndingHere + array[i];
if (maxEndingHere < 0) {
maxEndingHere = 0;
}
if (globalMaximum < maxEndingHere) {
//new max
globalMaximum = centerMax = maxEndingHere;
lowCenter = i;
}
}
//end center calc
//determine which range contains the maximum sub array
//if lowMidMax <= midHighMax and centerMax
if (lowMidMax >= midHighMax && lowMidMax >= centerMax) {
maxLowIndex = lowIndex;
maxHighIndex = mid;
//recursive call
findMaxSubArray(array, lowIndex, mid);
}
if (midHighMax >= lowMidMax && midHighMax >= centerMax) {
maxLowIndex = mid;
maxHighIndex = highIndex;
//recursive call
findMaxSubArray(array, mid, highIndex);
}
if (centerMax >= midHighMax && centerMax >= lowMidMax) {
maxLowIndex = lowCenter;
maxHighIndex = highCenter;
//recursive call
findMaxSubArray(array, lowCenter, highCenter);
}
}//end odd parent array length
}//end outer else array is ok to computed
}//end method
问题尽管与Kadane相比，全局最大和是正确的，但低指数和高指数范围反映了最后一次重复调用。
结果：使用数组子数组问题={100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97}；
Kadane（int array[]):1607低：0中：8 100，113，110，85，105，102，86，63，中+1:9高：16 101，94，106，101，79，94，90，97，低中心：16高中心：15
全局最大值不正确，注意差异实际上是1个元素，也就是81个元素
共有1个答案
宦源
寻找具有最大和的子数组的更干净的方法（D/C递归方式）：
// A Divide and Conquer based Java solution
// To find a subarray with the maximum sum
import java.util.Arrays;
import java.util.Scanner;
class MaxSubArray {
private static Result maxCrossingSum(int arr[], int l, int m, int h) {
int sum = 0;
int maxLeft = 0;
int leftSum = Integer.MIN_VALUE;
for (int i = m; i >= l; i--) {
sum = sum + arr[i];
if (sum > leftSum) {
leftSum = sum;
maxLeft = i;
}
}
sum = 0;
int rightSum = Integer.MIN_VALUE;
int maxRight = arr.length - 1;
for (int i = m + 1; i <= h; i++) {
sum = sum + arr[i];
if (sum > rightSum) {
rightSum = sum;
maxRight = i;
}
}
return new Result(maxLeft, maxRight, leftSum + rightSum);
}
private static Result maxSubArray(int[] A, int low, int high) {
if (low == high) {
return new Result(low, high, A[low]);
}
int mid = (low + high) / 2;
Result leftSubArray = maxSubArray(A, low, mid);
Result rightSubArray = maxSubArray(A, mid + 1, high);
Result maxCrossingSubArray = maxCrossingSum(A, low, mid, high);
int leftSum = leftSubArray.sum;
int rightSum = rightSubArray.sum;
int crossSum = maxCrossingSubArray.sum;
if (leftSum > rightSum && leftSum > crossSum) {
return new Result(leftSubArray.low, leftSubArray.high, leftSubArray.sum);
} else if (rightSum > leftSum && rightSum > crossSum) {
return new Result(rightSubArray.low, rightSubArray.high, rightSubArray.sum);
} else {
return new Result(maxCrossingSubArray.low, maxCrossingSubArray.high,
maxCrossingSubArray.sum);
}
}
public static class Result {
public int low;
public int high;
public int sum;
public Result(int low, int high, int sum) {
this.low = low;
this.high = high;
this.sum = sum;
}
}
/* Driver program to test maxSubArray */
public static Result maxSubArray(int[] arr) {
return maxSubArray(arr, 0, arr.length - 1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] arrString = sc.nextLine().split(" ");
int n = arrString.length;
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(arrString[i]);
}
Result result = maxSubArray(arr);
int[] subArray = new int[result.high - result.low + 1];
int j = 0;
for (int i = result.low; i <= result.high; i++) {
subArray[j++] = arr[i];
}
System.out.println(Arrays.toString(subArray));
System.out.println("Sum : " + result.sum);
}
}
类似资料：
-
任务给你一个排序的整数数组arr。它包含几个唯一的整数（负、正或零）。 您的任务是找到最大的d，使得a b c=d，其中a、b、c和d是arr的不同元素。如果没有找到这样的元素d，则返回null。 例子： 对于arr=[2,3,5,7,12]，输出应该是12（这个数组正确传递了我的函数） 对于arr=[-100，-1,0,7,101]，输出应该是0（这个不通过） 我可以进行正数检查，但我的函数因负
-
本文向大家介绍在数组中找到最大的d，使得C ++中的a + b + c = d，包括了在数组中找到最大的d，使得C ++中的a + b + c = d的使用技巧和注意事项，需要的朋友参考一下 假设我们有一组整数。我们必须找到一个数字“ d”，其中d = a + b + c，并且必须最大化（a + b + c），所有a，b，c和d都存在于集合中。该集合将至少容纳一个元素，最多可容纳1000个元素。每
-
我在读“算法导论”。在最大子数组问题（第4章）中，作者提出不能仅仅通过求子数组的最大值和最小值来计算股票买卖的最大利润。作者通过计算所有可能的买进和卖出日期的组合来谈到替代方案，例如蛮力，这将需要0(n^2)个时间。另一种选择是寻找价格日变化数组的最大子数组。 然而，我编写了一个算法，它将花费0(n)个时间，并找到最大利润。这是在0(n)对0(nlogn)的最大子数组问题。但我知道作者不会错的。我
-
给定一个整数数组，我必须找到具有最大和的子数组，使得和是奇数。 但是我怎么把它扩展到和是奇数。 编辑 数组的所有元素都是整数和正数
-
本文向大家介绍在C ++中使用分而治之算法的最大子数组总和，包括了在C ++中使用分而治之算法的最大子数组总和的使用技巧和注意事项，需要的朋友参考一下 假设我们有一个带有正值和负值的数据列表。我们必须找到其总和最大的连续子数组的总和。假设列表包含{-2，-5，6，-2，-3，1，5，-6}，则最大子数组的总和为7。它是{6，-2，-3的总和，1，5} 我们将使用分而治之方法解决此问题。步骤如下所示
-
我试图在一个数组中找到具有最大和的邻接子数组。所以，对于数组 {5,15,-30,10,-5,40,10}