歸并排序尋找和最大的子數組

1. 歸并法求解問題的最優解

基本思路：(1) 将一定規模的問題劃分為兩個規模相等的子問題；由兩個子問題的解可以求出該問題的最優解；

    (2) 劃分子問題的規模一直到不能劃分為止，即直到最小規模的子問題，然後将子問題的解組合成父問題的解。

2. 代碼如下：

#include <stdio.h>

#include <stdlib.h>

typedef struct Array

{

int left;

int right;

int sum;

}ARRAY,*ARRAYPOINT;

//此函數類似于歸并排序裡的合并函數

void FIND_MAX_CROSSING_SUBARRAY(int *A,int low,int mid,int high, ARRAY *max)

{

max->left=mid;

max->right=mid+1;

int left_sum=A[mid];

int sum = left_sum;

for(int i=mid-1;i>=low;--i)

{

sum += A[i];

if(sum > left_sum)

{

left_sum=sum;

max->left=i;

}

}

max->sum = left_sum;

int right_sum = A[mid+1];

sum = right_sum;

for(int j=mid+2;j<=high;++j)

{

sum+=A[j];

if (sum > right_sum)

{

right_sum = sum;

max->right = j;

}

}

max->sum += right_sum;

return ;

}

void FIND_MAXIMUM_SUBARRAY(int *A,int low,int high, ARRAY *max)

{

if(low==high)

{

max->left=max->right=low;

max->sum=A[low];

return ;

}

else

{

int mid=(low+high)/2;

ARRAY left_max,right_max,cross_max;

FIND_MAXIMUM_SUBARRAY(A,low,mid, &left_max);

FIND_MAXIMUM_SUBARRAY(A,mid+1,high, &right_max);

//類似于歸并排序裡的合并

FIND_MAX_CROSSING_SUBARRAY(A,low,mid,high, &cross_max);

if(left_max.sum>=right_max.sum&&left_max.sum>=cross_max.sum) {

max->left = left_max.left;

max->right = left_max.right;

max->sum = left_max.sum;

}

else if(right_max.sum>=left_max.sum&&right_max.sum>=cross_max.sum) {

max->left = right_max.left;

max->right = right_max.right;

max->sum = right_max.sum;

}

else {

max->left = cross_max.left;

max->right = cross_max.right;

max->sum = cross_max.sum;

}

return ;

}

}

int main(void)

{

int A[]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22};

ARRAY  max;

FIND_MAXIMUM_SUBARRAY(A,0,sizeof(A)/sizeof(A[0])-1, &max);

printf("最大子數組從第%d個元素開始，到第%d個元素結束\n",max.left+1,max.right+1);

printf("其和為：%d\n",max.sum);

return 0;

} 

3. 本部落格參考http://www.fx114.net/qa-115-367694.aspx

本部落格貼的代碼經過測試，可以直接運作輸出正确結果