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; 
    } 
} 

我得到這個作爲輸出

有人能幫助我嗎？

Answer 1

maxsub（...）中的遞歸初始輸出錯誤，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. 
}