【算法導論】最大子數組問題

       在算法導論中，最大子數組問題是在股票買賣的背景下提出來的。顯然，我們都希望可以在“低位買進，高位賣出”，這樣獲利是最多的。不過，其實這算法對于實際操作也沒多大意義，因為，你根本不知道目前的價錢是高位，還是低位。或許可以用ML的方法去學習出未來一天股價大漲還是大跌的特征，就可以預測未來，實際上應該也有人嘗試過。不過估計是學不到很好的特征的，畢竟影響因素太多了。

       例如下圖放映了某隻股票在17天内的股價變化，如果你可以在第7天之後買進，第11天賣出，那麼收益是很可觀的，可以達到43，在這17天内沒有更好的組合來使得利益最大化了。

       要怎麼求解這個問題呢？最直接的方法也是最暴力的方法--排列組合，把所有情況都拿去算一遍，然後把好的留下來。當然，問題是可以解決的，但是，複雜度太高了，是o（n^2）。換個角度，把每天的股價換成和前一天的差來組織資料，那麼這麼多天的資料其實就構成一個數組A，我們要的是找出這個數組A的一個子數組，這個子數組的和最大，這問題就叫做最大子數組（maximum subarray）問題。

       本文介紹一種高效的求解方法，來找到一個最大子數組。為什麼強調“一個最大子數組”，因為有時候答案并不唯一。例如，股價連續幾天一樣，那麼這些天裡哪天買進都不影響結果。我們使用分治政策來求解這個問題。問什麼要用分治算法，其實也就是為了降低複雜度。要在一個大數組找子數組，可以考慮兩個長度更小的子數組中分别找到最大子數組，假如可以這兩個子數組是可以連起來的，那麼合起來就是答案了。下面了解一下下面的結論：

如果把數組A分成兩個子數組A1和A2，A1=A[low,mid]，A2=A[mid+1,high]，其中low和high分别是A的最大和最小下标，mid=（low+high）/2，向上向下取整都一樣，那麼A[low,high]的任何子數組A[i,j]必然是以下三種情況之一：

（1）完全位于子數組A[low,mid]中,low<=i<=j<=mid；

（2）完全位于子數組A[mid+1,high]中,mid+1<=i<=j<=high；

（3）跨越了中點，是以low<=i<mid<=j<=high；

       容易看到，如果把兩個子數組繼續分下去，就可以分成4個，然後是8個，一直分下去，直到low=i=j=high就不可可以再分了。把大問題分解成小問題求解，然後再把小問題的解合并起來，就是分治政策的思想。本問題和其他分治問題不同的地方在于，不是簡單地把大問題當成小規模問題的示例，合并的條件是必須跨越中點。

       下面給出上面問題求解的c源代碼，關鍵的地方是一下幾句代碼：

threeParmLeft=findMaxinumSubarray(number,low,mid);      

threeParmRight=findMaxinumSubarray(number,mid+1,high);      

threeParmCross=findMaxCrossingSubarray(number,low,mid,high);      

#include <stdio.h>
#define LENGTH 16
//定義一個結構，記錄了左右下表和總和，原因在于用于資料返還
typedef struct
   {
     int low;
     int high;
     int sum;
   }parm;

parm findMaxCrossingSubarray(int number[],int low,int mid,int high);
parm findMaxinumSubarray(int number[],int low,int high);

int main()
{
    int number[LENGTH] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};

    parm threeParm;
    threeParm=findMaxinumSubarray(number,0,LENGTH-1);
    printf("%d,%d,%d",threeParm.low,threeParm.high,threeParm.sum);
    return 0;

}
parm findMaxinumSubarray(int number[],int low,int high)
{
    int mid;
    parm threeParmLeft;
    parm threeParmRight;
    parm threeParmCross;
    parm threeParm;
//遞歸停止條件
    if (low==high)
    {
        threeParm.low=low;
        threeParm.high=high;
        threeParm.sum=number[low];
        return threeParm;
    }
    else
    {
        //分治政策        
        mid=(low+high)/2;

        threeParmLeft=findMaxinumSubarray(number,low,mid);
        threeParmRight=findMaxinumSubarray(number,mid+1,high);
        threeParmCross=findMaxCrossingSubarray(number,low,mid,high);
        //下标更新        
        if (threeParmLeft.sum>threeParmRight.sum&&threeParmLeft.sum>threeParmCross.sum)
            return threeParmLeft;
        else if (threeParmRight.sum>threeParmLeft.sum&&threeParmRight.sum>threeParmCross.sum)
              return threeParmRight;
        else
            return threeParmCross;
      }
}
parm findMaxCrossingSubarray(int number[],int low,int mid,int high)
{
    int i;
    parm threeParm;
    //左搜尋
    int sum=0;
    int leftSum=number[mid]-1;
    int left;

    for (i=mid;i>=low;i--)
    {
        sum=sum+number[i];
        if(sum>leftSum)
        {
            leftSum=sum;
            left=i;
        }
    }
    //右搜尋
    sum=0;
    int rightSum=number[mid+1]-1;
    int right;
    for (i=mid+1;i<=high;i++)
    {
        sum=sum+number[i];
        if(sum>rightSum)
        {
            rightSum=sum;
            right=i;
        }
    }
    threeParm.low=left;
    threeParm.high=right;
    threeParm.sum=leftSum+rightSum;
    return threeParm;
}