最大子數組和分治與暴力求解法

最大子數組和分治與暴力求解法

簡單寫了求連續子數組的最大和的算法。枚舉法時間復雜度為nlgn，暴力法為n^2。但當n比較小的時候，暴力法更為有效，一直很好奇比較小是小到什麼程度，故寫了程序測試下。

先看暴力求解法

int FindMaxSubArrayViolently(int a[],int high,int &p,int &q)//high為數組a未下標，p與q用應用類型保存最大連續子數組的起始下標與末小標
{
    int sum_max=-INFINITE,sum;
    for(int i=0;i<high-1;i++)
        for(int j=i,sum=a[j];j<high;sum+=a[++j])
            if(sum>sum_max)
            {
                sum_max=sum;
                p=i;q=j;
            }
    return sum_max;
}

分治法

思路：子數組必然是三種情況之一：

1、在子數組a[low...mid]中

2、在a[mid+1...high]中

3、跨越中點

前兩種好解決，將數組a[low...high]二分，遞歸到當low>=high時返回a[low]為最大連續子數組只有一個的情況下本身為最大連續子數組）。第三種可以先求得mid點左右兩邊的最大連續子數組，再相加起來，代碼如下：

int FindMaxSubArray(int a[],int low,int high,int &p,int &q)
{
    if (low==high)
    {
        p=q=low;
        return a[low];
    }
    else
    {
        int mid=(low+high)/2,left_low,left_high,left_sum,right_low,right_high,right_sum,cross_low,cross_high,cross_sum;
        left_sum=FindMaxSubArray(a,low,mid,left_low,left_high);
        right_sum=FindMaxSubArray(a,mid+1,high,right_low,right_high);
        cross_sum=FindMaxCrossingSubArray(a,low,high,cross_low,cross_high);
        if(left_sum>=right_sum && left_sum>=cross_sum)
        {
            p=left_low;q=left_high;
            return left_sum;
        }
        else if(right_sum>=left_sum && right_sum>=cross_sum)
        {
            p=right_low;q=right_high;
            return right_sum;
        }
        else
        {
            p=cross_low;q=cross_high;
            return cross_sum;
        }
    }
}

求跨越中點時的情況：

int FindMaxCrossingSubArray(int a[],int low,int high,int &p,int &q)
{
    int sum_left,sum_right,sum=0,i,max_left,max_right,mid=(low+high)/2;
    sum_left=sum_right=-INFINITE;
    for(i=mid,sum=a[mid];i>=low;sum+=a[--i])
        if(sum>sum_left)
        {
            sum_left=sum;
            max_left=i;
        }
    for(i=mid+1,sum=a[i];i<=high;sum+=a[++i])
        if(sum>sum_right)
        {
            sum_right=sum;
            max_right=i;
        }
    p=max_left;q=max_right;
    return sum_left+sum_right;
}

接下來寫一個隨機數發生器來產生測試數據：

void GenerateRandNum(int a[],int n)
{
    srand(n);
    for(int i=0;i<n;i++)
        a[i]=-rand()%2000+1000;
}

再接下來調用windows api來測試時間：

int main()
{
    DWORD start,end,t1,t2;
    int a[MAXN],low,high,sum,n=10;
    t1=t2=0;
    while(n<MAXN && t2>=t1)
    {
        GenerateRandNum(a,n);
        start=GetTickCount();
        sum=FindMaxSubArrayViolently(a,n-1,low,high);
        end=GetTickCount();
        t1=end-start;
/*----------------------------------------------------------------*/
        GenerateRandNum(a,n);
        start=GetTickCount();
        sum=FindMaxSubArray(a,0,n-1,low,high);
        end=GetTickCount();
        t2=end-start;
        n+=10;
    }
    printf("%d",n);
    return 0;
}

測試結果比我想象的要小，大約n在400~500之間分治法效果就比暴力法好了。

本文出自 “卡薩布蘭卡” 博客，請務必保留此出處http://vinttwade.blog.51cto.com/7772448/1277330