学步园

    算法导论第四章的最大子数组问题，暴力求解的时间复杂度为Θ(n²)，递归时间复杂度为Θ(nlgn)；书上提示还存在一个不使用分治的线性时间算法。可惜太菜，慢慢进步

暴力求解版:

// 最大子数组(暴力求解) -- 2014/04/12	13:51
#include <stdio.h>
#include <limits.h>	// INT_MIN

struct max_Subarray	
{
	int data;		// 最大子数组的和值
	int max_Left;	// 最大子数组的左边界
	int max_Right;	// 最大子数组的右边界
};

struct max_Subarray max_S[17];	

struct max_Subarray Find_Maximum_Subarray(int * arr, int low, int high);

int main()
{
	int arr[17] = {0, 13, -3, -25, 20,  -3, -16, -23, 18,
				   20, -7,  12, -5, -22,  15,  -4,  7};
	
	struct max_Subarray temp;	// 保存函数返回的最大子数组结构体

	temp = Find_Maximum_Subarray(arr, 1, 16);

	printf("最大子数组的和值为:%d\n", temp.data);
	printf("最大子数组的左边界:%d	右边界为:%d\n", temp.max_Left, temp.max_Right);

	return 0;
}

struct max_Subarray Find_Maximum_Subarray(int * arr, int low, int high)
{
	struct max_Subarray max_Sub;
	int i, j, sum;
	int left_Sum, right_Sum;

	for (i = low; i <= high; i++)
	{
		left_Sum  = INT_MIN;
		right_Sum = INT_MIN;

	 // 以arr[i]为参照，左右寻找最大子数组的边界，并计算和值
	 // 左边
		sum = 0;
		for (j = i; j >= low; j--)	
		{
			sum = sum + arr[j];		
			if (sum > left_Sum)		// 如果新加入的元素使得sum>left_Sum，则更新left_Sum并记录左边界
			{
				left_Sum = sum;
				max_S[i].max_Left = j;
			}
		}
	 // 右边
		sum = 0;
		for (j = i; j <= high; j++)
		{
			sum = sum + arr[j];
			if (sum > right_Sum)	// 如果新加入的元素使得sum>left_Sum，则更新left_Sum并记录右边界
			{
				right_Sum = sum;
				max_S[i].max_Right = j;
			}
		}

	 // 左右两边都是以i为起点，所以和值要减去arr[i]本身
		max_S[i].data = left_Sum + right_Sum - arr[i];
	}

 // 在max_S[]数组中找出max_S[i].data值最大的结构体，函数返回此结构体
	max_Sub.data = INT_MIN;		// 初始化为负无穷
	for (i = 1; i <= 16; i++)
		if (max_S[i].data > max_Sub.data)
			max_Sub = max_S[i];

	return max_Sub;
}

递归版:

// 最大子数组(递归) -- 2014/04/12 -- 10:10
#include <stdio.h>
#include <limits.h>

int left_Sum, right_Sum, cross_Sum;	// 分别存储三种情况下最大子数组的和值
int max_Left, max_Right;			// 最大子数组的左右边界

int Find_Maximum_Subarray(int * arr, int low, int high);	// 寻找最大子数组的递归函数
// 寻找跨越中点的最大子数组
int Find_Max_Crossing_Subarray(int * arr, int low, int mid, int high);

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

	number = Find_Maximum_Subarray(arr, 1, 16);

	fprintf(stdout, "找到的最大子数组的和值为%d\n", number);
	fprintf(stdout, "最大子数组的左右边界分别为: %d %d\n", max_Left, max_Right);

	return 0;
}

int Find_Max_Crossing_Subarray(int * arr, int low, int mid, int high)
{
	int sum, i, j;

	left_Sum = -INT_MAX;	// 初始化为负无穷，保证更新左和值
	sum = 0;
	for (i = mid; i >= low; i--)
	{
		sum = sum + arr[i];
		if (sum > left_Sum) // 如果加入新元素后大于上一次的最大和值
		{
			left_Sum = sum; // 更新和值
			max_Left = i;	// 记录左下标
		}
	}

	right_Sum = -INT_MAX;	// 初始化为负无穷，保证更新左和值
	sum = 0;
	for (j = mid+1; j <= high; j++)
	{
		sum = sum + arr[j];
		if (sum > right_Sum) // 如果加入新元素后大于上一次的最大和值
		{
			right_Sum = sum; // 更新和值
			max_Right = j;	 // 记录右下标
		}
	}

 // 返回跨越中点的最大子数组值的和
	return (left_Sum + right_Sum);
}

int Find_Maximum_Subarray(int * arr, int low, int high)
{
	int mid;

	if (low == high)			// 寻找区间只有一个元素
		return (arr[low]);	
	else
	{
		mid = (low+high) / 2;	// 分解递归
		left_Sum  = Find_Maximum_Subarray(arr, low, mid);
		right_Sum = Find_Maximum_Subarray(arr, mid+1, high);
		cross_Sum = Find_Max_Crossing_Subarray(arr, low, mid, high);

	 // 分别返回三种情况(最大子数组在左边，跨越中点，右边)下的最大子数组和值
		if (left_Sum>=right_Sum && left_Sum>=cross_Sum)
			return left_Sum;
		else if (right_Sum>=left_Sum && right_Sum>=cross_Sum)
			return right_Sum;
		else
			return cross_Sum;
	}
}

   最后关于代码的注释(多是高手的代码)，附上几点小感悟：

① 不要被代码中各种“高级”，莫名其妙的术语吓到，重点放在调试分析代码。

② 所谓无穷值，其实一般就是数据类型所能表示的最大值，比如int的正无穷：INT_MAX，int的负无穷：INT_MIN。

③ 多和小伙伴们讨论问题，IT的领域无穷无尽呐！没有小伙伴就依赖搜索框，有时会得到意外惊喜的答案