算法导论学习：分治策略之最大子数组问题

        对于分治策略，是算法中很重要的一个环节，它能够将一个很大的问题分解为一个个的小问题，从而降低求解难度。今天，我就对《算法导论》中的最大字数组问题进行分析，并给出书中伪代码的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倍，可见分治递归算法的效率。今天的学习就到这里，好累。