学步园

方法1：暴力法

遍历数组三次(i in 0..len, j in i..len, k in i..j)，在第三次(k in i..j)求和sum+=data[k]，并与当前max比较，大则更新max值，小max值不变

时间复杂度为O(n^3);

具体代码实现：

int max(int a, int b)	{	return (a>b ? a : b); }

int max_sub_sum(int *data, int len)
{
	int sum=0, maxsofar=0;
	int i=0, j=0, k=0;
	for(i=0; i<=len; i++)
	{
		for(j=i; j<=len; j++)
		{
			sum=0;
			for(k=i; k<=j; k++)
			{
				sum += data[k];
				maxsofar = max(maxsofar, sum);
			}
		}
	}
	return maxsofar;
}

int main(void)
{
	const int SIZE = 1000;
	int i=0;
	int data[1000];
	FILE *fp;
	fp = fopen("data1.txt", "r");
	while(!feof(fp))
	{
		if(feof(fp))	break;
		fscanf(fp, "%d", &data[i++]);
	}	
	struct timeval start,end;
	gettimeofday(&start, NULL);
	int max_sum = max_sub_sum(data, SIZE-1);
	gettimeofday(&end, NULL);
	float t_time = end.tv_sec-start.tv_sec + (end.tv_usec-start.tv_usec)/1000000.0;
	cout << "time used: " << t_time << endl;
	cout << "the max is : " << max_sum << endl;
	return 0;
}

方法二：用分治算法解决

一个数组的最大字数组就存在于数组的三个位置，要么在数组的左半边，要么在数组的右半边，要么在数组的中间，而在数组的左右半边也符合该算法，可以用分治算法来解决

即 max_sum = max(left_max+right_max, max_sub_sum(l,m), max_sub_sum(m+1, h))   //m为每次数组的中间位置

时间复杂度为O(n*logn)

具体代码如下：

int max_two(int a, int b)	{	return (a>b ? a : b) ;	}
int max_three(int a, int b, int c)
{
	int max, temp[3] = {a, b, c};
	max = temp[0];	
	for(int i=0; i<3; i++)
	{
		if(temp[i]>max)
			max = temp[i];
	}
	return max;
}

int max_sub_sum(int *data, int l, int h)
{
	if(l>h)		return 0;
	if(l==h)	return max_two(data[0], 0);
	int left_max=0, right_max=0, sum=0;
	int i=0, m=(h+l)/2;
	for(i=m; i>=l; i--)
	{
		sum += data[i];
		left_max = max_two(left_max, sum);
	}
	sum = 0;
	for(i=m+1; i<=h; i++)
	{
		sum += data[i];
		right_max = max_two(right_max, sum);
	}
	return max_three(left_max+right_max, max_sub_sum(data, l, m), max_sub_sum(data, m+1, h));
}

方法三：遍历数组一遍，使用两个变量:maxendinghere 记录遍历过的元素之和与0比较后的最大值

maxsofar 记录当前字数组的最大值max(maxsofar, maxendinghere)，与maxendinghere比较后的最大值

时间复杂度为O(n)

具体代码如下：

int max(int a, int b)	{	return (a>b ? a : b); }

int max_sub_sum(int *data, int len)
{
	int maxsofar=0, maxendinghere=0;
	for(int i=0; i<=len; i++)
	{
		maxendinghere = max(maxendinghere+data[i], 0);
		maxsofar = max(maxsofar, maxendinghere);
	}
	return maxsofar;
}

对三种方法的运行时间进行比较，数组元素个数为1000