java - 使用分而治之的 Maxsub 数组

Question

我在使用分治法实现最大子数组问题时遇到了问题。

假设我有一个数组 [3,6,-1,2]，我想按连续顺序找到这个数组的最大总和。我们可以看一下 [0,3] 的和是 10。

我尝试实现我书中的伪代码，但答案不正确。

// return (max-left, max-right, max sum left + right)
public static int[] maxcross(int[] array, int low, int mid, int high) {
    int leftSum = -10000000;
    int rightSum = -10000000;
    int sum = 0;
    int maxLeft=0;
    int maxRight=0;
    for(int i=mid;i<mid-low;i--){
        sum = sum + array[i];
        if(leftSum < sum){
            leftSum = sum;
            maxLeft = i;
        }
    }
    sum=0;
    for(int i=mid+1;i<high;i++){
        sum = sum + array[i];
        if(rightSum < sum){
            rightSum = sum;
            maxRight = i;
        }
    }
    int cross[] = {maxLeft,maxRight,leftSum+rightSum};
    return cross;
}

public static int[] maxsub(int array[], int low, int high){
    int[] maxSubLeft = new int[3];
    int[] maxSubRight = new int[3];
    int[] maxSub = new int[3];
    int[] maxSubCross = new int[3];
    int mid;
    if (high==low){
        maxSub[0] = low;
        maxSub[1] = high;
        maxSub[2] = array[low];
        return maxSub;
    }
    else{
        mid = (int) Math.floor((low+high)/2);
        maxSubLeft = maxsub(array,low,mid);
        maxSubRight = maxsub(array,mid+1,high);
        maxSubCross = maxcross(array,low,mid,high);

        if(maxSubLeft[2] >= maxSubRight[2] && maxSubLeft[2] >= maxSubCross[2])
            return maxSubLeft;
        else if(maxSubRight[2] >= maxSubLeft[2] && maxSubRight[2] >= maxSubCross[2])
            return maxSubRight;
        else
            return maxSubCross;
    }
}

我得到这个作为输出

1

1

6

有人可以帮助我吗？

Answer 1

maxsub(...) 中的递归初始输出错误，返回 0 当 high=low 和 array[low] < 0;

public static int[] maxsub(int array[], int low, int high){
    int[] maxSubLeft = new int[3];
    int[] maxSubRight = new int[3];
    int[] maxSub = new int[3];
    int[] maxSubCross = new int[3];
    int mid;
    if (high==low){
        maxSub[0] = low;
        maxSub[1] = high;
        maxSub[2] = array[low];
        return maxSub; // if (array[low] < 0) return 0;
    }
    else{
        mid = (int) Math.floor((low+high)/2);
        maxSubLeft = maxsub(array,low,mid);
        maxSubRight = maxsub(array,mid+1,high);
        maxSubCross = maxcross(array,low,mid,high);

        if(maxSubLeft[2] >= maxSubRight[2] && maxSubLeft[2] >= maxSubCross[2])
            return maxSubLeft;
        else if(maxSubRight[2] >= maxSubLeft[2] && maxSubRight[2] >= maxSubCross[2])
            return maxSubRight;
        else
            return maxSubCross;
    }
}

顺便说一句，你的递归算法是O(NlnN)，更有效和更容易实现的算法是O(N)，它应用了动态规划。

public static int maxSum(int array[], int low, int high) {
   int maxsum = 0, maxleftsum = 0;
   for (int i = low; i < high; i++) {
       maxsum = max(maxsum, array[i] + maxleftSum);
       maxleftSum = max(0, maxleftSum+array[i]);
   }
   return maxsum; // return the index if necessary. 
}