算法導論學習：分治政策之最大子數組問題

        對于分治政策，是算法中很重要的一個環節，它能夠将一個很大的問題分解為一個個的小問題，進而降低求解難度。今天，我就對《算法導論》中的最大字數組問題進行分析，并給出書中僞代碼的C/C++語言表現形式，同時給出一個暴力求解最大子數組問題的C代碼。

第四章 分治政策

1.最大子數組問題

          最大子數組問題定義：給出一個數組，求出數組中連續數組元素之和最大的子數組。這個問題可以從股票上面概括分析得之，參見《算法導論》，這裡不再贅述。

          下面，我将給出暴力求解方法和遞歸算法兩種實作形式。

（1）暴力求解C/C++語言實作形式

        書中給出了遞歸求解的僞代碼，并未給出暴力求解的算法，這裡，我自己謝了一個簡單的求解算法，這個算法将在後面與遞歸算法進行運算比較，給出比較時間，這裡給出實作的函數。

/**************************************************************************************
*  函數功能：暴力求解最大子數組                              *
*  參數入口：Data為數組，low,high為數組邊界，*left,*right為傳回的左右邊界         *
*  傳回值：  傳回值為最大子數組的和                         *
**************************************************************************************/
int Force_search(int *Data, int low, int high, int *left, int *right)
{
    int sum=-1000000;                 //設定一個小的初始值。
    int sum_temp;                   //臨時元素和變量。
    for(int i=low;i<=high;i++)            //尋找最大子數組，采用周遊的方式，依次尋找。
    {
        sum_temp=0;
        for(int j=i;j<=high;j++)
        {
            sum_temp+=Data[j];
            if(sum_temp>sum)
            {
                sum=sum_temp;           //記錄下目前最大元素和與子數組邊界。
                *left=i;
                *right=j;
            }
        }
    }
    return sum;
}
           

（2）遞歸求解最大子數組C/C++語言實作代碼

         遞歸實作代碼根據《算法導論》中僞代碼，以C語言形式實作。

/**************************************************************************************
*  函數功能：尋找處于中間位置的最大子數組                                             *
*  參數入口：Data為數組，low,mid,high為三個邊界，*left,*right為傳回的左右邊界         *
*  傳回值：  傳回值為最大子數組的和                                                   *
**************************************************************************************/
int Find_max_crossing_subarray(int *Data, int low, int mid, int high, int *left, int *right)
{
	int left_sum=-1000000;   //先設定初值，最小值。
	int sum=0;
	for(int i=mid;i>=low;i--)    //尋找左邊最大值子數組。
	{
		sum+=Data[i];
		if(sum>left_sum)
		{
			*left=i;
			left_sum=sum;
		}
	}
	int right_sum=-1000000;
	sum=0;
	for(int i=mid+1;i<=high;i++)   //尋找右邊最大子數組。
	{
		sum+=Data[i];
		if(sum>right_sum)
		{
			*right=i;
			right_sum=sum;
		}
	}
	return (left_sum+right_sum);
}

/**************************************************************************************
*  函數功能：遞歸尋找最大子數組                                                       *
*  參數入口：Data為數組，low,high為數組邊界，*left,*right為傳回的左右邊界             *
*  傳回值：  傳回值為最大子數組的和                                                   *
**************************************************************************************/
int Find_maximum_subarray(int *Data, int low, int high, int *left, int *right)
{
	if(low==high)
	{
		*left=low;
		*right=high;
		return Data[low];
	}
	else
	{
		int mid=(low+high)/2;    //尋找中間值。

		int *left_low=(int*)malloc(sizeof(int));
	    int *left_high=(int*)malloc(sizeof(int));
		int left_sum=Find_maximum_subarray(Data, low, mid, left_low, left_high);    //計算左邊最大子數組。

		int *right_low=(int*)malloc(sizeof(int));
	    int *right_high=(int*)malloc(sizeof(int));
		int right_sum=Find_maximum_subarray(Data, mid+1, high, right_low, right_high);  //計算右邊最大子數組。

		int *cross_low=(int*)malloc(sizeof(int));
	    int *cross_high=(int*)malloc(sizeof(int));
		int cross_sum=Find_max_crossing_subarray(Data, low, mid, high, cross_low, cross_high);  //計算中間最大子數組。

		if(left_sum>right_sum && left_sum>cross_sum)
		{
			*left=*left_low;
			*right=*left_high;
			return left_sum;
		}
		else 
			if(right_sum>left_sum && right_sum>cross_sum)
			{
				*left=*right_low;
				*right=*right_high;
				return right_sum;
			}
			else
			{
				*left=*cross_low;
				*right=*cross_high;
				return cross_sum;
			}
	}
}
           

（3）兩種算法運作時間比較

          為了直覺的比較兩種算法運作時間，我們随機産生100000個元素的數組，分别采用兩種方法運作，程式與運作結果如下：下面代碼中缺少上面給出的兩個子函數，隻要将上面給出的函數加入其中即可。

#include<windows.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define LENGTH 100000

void Time_calculate(int start_time)
{
	int end_time=GetTickCount();
	printf("開始時間：%d\n",start_time);
	printf("結束時間：%d\n",end_time);
	int spend_time=end_time-start_time;
	int out_s=spend_time/1000;
	int out_ms=spend_time%1000;
	printf("花費時間：%d s %d ms\n",out_s,out_ms);

}    

/*************************測試尋找最大子數組函數******************************/
void test_max_array(void)
{
//  int Data[16]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
	int* Data=(int*)malloc(sizeof(int)*LENGTH);
	srand((unsigned)time(NULL)); 
	for(int i=0;i<LENGTH;i++)                      //随機産生随機數
	{
		int flag=rand()%2;
		int temp=rand()%100;   
		if(flag==0)
			Data[i]=0-temp;
		else
			Data[i]=temp;
	}
	printf("\n随機産生100個數：\n");
	for(int i=0;i<LENGTH;i++)                     
	{
		if(i%10==0)
			printf("\n");
		printf("%d  ",Data[i]);
	}    

	int *left=(int*)malloc(sizeof(int));
	int *right=(int*)malloc(sizeof(int));

	int start_time=GetTickCount();   //記錄開始時間

	int sum=Find_maximum_subarray(Data, 0, LENGTH-1, left, right);  
	printf("\n\n分治求解答案:\nleft=%d\nright=%d\nsum=%d\n\n",*left,*right,sum);

	Time_calculate(start_time);       //列印結束時間
	start_time=GetTickCount();   //記錄開始時間

	int sum_force=Force_search(Data, 0, LENGTH-1, left, right);
	printf("\n暴力求解答案:\nleft=%d\nright=%d\nsum_force=%d\n\n\n\n",*left,*right,sum_force);

	Time_calculate(start_time);     //列印結束時間。

	free(left);
	free(right);
}

int main(void)
{
	
	test_max_array();
	return 0;
}

           

           從運作結果可以看出，對100000個元素的數組來說，遞歸求解時間僅為125ms，而暴力求解方式時間為14s 711ms，時間将近118倍，可見分治遞歸算法的效率。今天的學習就到這裡，好累。