算法導論尋找最大子數組

算法導論在講解分治算法中第二個典型的例子，在一個數組中尋找最大子數組。即在這個數組中找到連續加和最大的部分！
我們先分析該問題，能夠發現如果將數組分成兩部分，尋找到每一部分的最大子數組和跨越兩部分的最大子數組，即為該問題的完全解。

我們發現最復雜部分是跨越兩部分的最大子數組，我們先來解決這部分的問題。

首先先看代碼：

[cpp]

[cpp]
<SPAN style="FONT-SIZE: 18px">int Find_MAX_CROSSING_SUBARRAY(int *A,int low,int mid,int high,int& max_left,int& max_right,int& max_value) 
{ 
    int left_sum= -1000000;//不可能的最小值  
    int sum = 0; 
     
    for(int i= mid;i>low;i--) 
    { 
        sum = sum+A[i]; 
        if(sum>left_sum) 
        { 
            left_sum = sum; 
            max_left=i; 
        } 
    } 
     
    int right_sum = -1000000;//不可能的最小值  
    sum =0; 
     
    for(int j=mid+1;j<high;j++) 
    { 
        sum = sum+A[j]; 
        if(sum>right_sum) 
        { 
            right_sum = sum; 
            max_right =j; 
        } 
    } 
     
    max_value = left_sum+right_sum; 
    return 0; 
}</SPAN> 

int Find_MAX_CROSSING_SUBARRAY(int *A,int low,int mid,int high,int& max_left,int& max_right,int& max_value)
{
 int left_sum= -1000000;//不可能的最小值
 int sum = 0;
 
 for(int i= mid;i>low;i--)
 {
  sum = sum+A[i];
  if(sum>left_sum)
  {
   left_sum = sum;
   max_left=i;
  }
 }
 
 int right_sum = -1000000;//不可能的最小值
 sum =0;
 
 for(int j=mid+1;j<high;j++)
 {
  sum = sum+A[j];
  if(sum>right_sum)
  {
   right_sum = sum;
   max_right =j;
  }
 }
 
 max_value = left_sum+right_sum;
 return 0;
}

從算法上看到，我們依然放入了兩個不可能的哨兵值。上面代碼中 每一行都已經很清晰，這裡就不做分析了，不懂的童鞋可以留言。然後我們來寫函數的遞歸部分，退出遞歸的條件是關鍵，試想如果low和high是同一個值我們該如何求最大子數組，這當然是廢話，直接返回這個值就好了，所以算法就這樣搞定了，然後貼出代碼：

[cpp]
int Find_MaxiMum_SubArray(int *A,int low,int high,int& max_left,int& max_right,int& max_value) 
{ 
    if(high==low) 
    { 
        max_left  = low; 
        max_right = high; 
         
        max_value = A[low]; 
    } 
    else 
    { 
        int mid=(low+high)/2; 
         
        int tmp_left_low; 
        int tmp_left_high; 
        int tmp_left_sum; 
         
        Find_MaxiMum_SubArray(A,low,mid,tmp_left_low,tmp_left_high,tmp_left_sum); 
         
        int tmp_right_low; 
        int tmp_right_high; 
        int tmp_right_sum; 
         
        Find_MaxiMum_SubArray(A,mid+1,high,tmp_right_low,tmp_right_high,tmp_right_sum); 
         
        int tmp_cross_low; 
        int tmp_cross_high; 
        int tmp_cross_sum; 
         
        Find_MAX_CROSSING_SUBARRAY(A,low,mid,high,tmp_cross_low,tmp_cross_high,tmp_cross_sum); 
         
        if ((tmp_left_sum>=tmp_right_sum)&&(tmp_left_sum>=tmp_cross_sum)) 
        { 
            max_left    = tmp_left_low; 
            max_right   = tmp_left_high; 
            max_value   = tmp_left_sum; 
        } 
        else if((tmp_right_sum>=tmp_left_sum)&&(tmp_right_sum>=tmp_cross_sum)) 
        { 
            max_left    = tmp_right_low; 
            max_right   = tmp_right_high; 
            max_value   = tmp_right_sum; 
        } 
        else 
        { 
            max_left    = tmp_cross_low; 
            max_right   = tmp_cross_high; 
            max_value   = tmp_cross_sum; 
        } 
         
    } 
     
    return 0; 
} 

int Find_MaxiMum_SubArray(int *A,int low,int high,int& max_left,int& max_right,int& max_value)
{
 if(high==low)
 {
  max_left  = low;
  max_right = high;
  
  max_value = A[low];
 }
 else
 {
  int mid=(low+high)/2;
  
  int tmp_left_low;
  int tmp_left_high;
  int tmp_left_sum;
  
  Find_MaxiMum_SubArray(A,low,mid,tmp_left_low,tmp_left_high,tmp_left_sum);
  
  int tmp_right_low;
  int tmp_right_high;
  int tmp_right_sum;
  
  Find_MaxiMum_SubArray(A,mid+1,high,tmp_right_low,tmp_right_high,tmp_right_sum);
  
  int tmp_cross_low;
  int tmp_cross_high;
  int tmp_cross_sum;
  
  Find_MAX_CROSSING_SUBARRAY(A,low,mid,high,tmp_cross_low,tmp_cross_high,tmp_cross_sum);
  
  if ((tmp_left_sum>=tmp_right_sum)&&(tmp_left_sum>=tmp_cross_sum))
  {
   max_left = tmp_left_low;
   max_right  = tmp_left_high;
   max_value  = tmp_left_sum;
  }
  else if((tmp_right_sum>=tmp_left_sum)&&(tmp_right_sum>=tmp_cross_sum))
  {
   max_left = tmp_right_low;
   max_right  = tmp_right_high;
   max_value  = tmp_right_sum;
  }
  else
  {
   max_left = tmp_cross_low;
   max_right  = tmp_cross_high;
   max_value  = tmp_cross_sum;
  }
  
 }
 
 return 0;
}
後邊我再寫了一個調用的代碼：

[cpp]
int B[10] = {1,-10,2,4,6,-15,6,1,9,-8}; 
 
int main(int argc, char **argv) 
{ 
 
    cout<<endl; 
     
    int max_left,max_right,max_value; 
    Find_MaxiMum_SubArray(B,0,10,max_left,max_right,max_value); 
    cout<< max_left<<"\t"<<max_right<<"\t"<<max_value<<endl; 
    cout<<endl; 
    system("pause"); 
    return 0; 
} 

int B[10] = {1,-10,2,4,6,-15,6,1,9,-8};

int main(int argc, char **argv)
{

 cout<<endl;
 
 int max_left,max_right,max_value;
 Find_MaxiMum_SubArray(B,0,10,max_left,max_right,max_value);
 cout<< max_left<<"\t"<<max_right<<"\t"<<max_value<<endl;
 cout<<endl;
 system("pause");
 return 0;
}
好了，這個算法是分治算法的另一種典型的例子。因為再進行遞歸的時候要分情況遞歸，O(∩_∩)O~。