雅乐网

输入一组整数，求出这组数字子序列和中最大值。也就是只要求出最大子序列的和，不必求出最大的那个序列。例如：

序列：-2 11 -4 13 -5 -2，则最大子序列和为20。

序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，则最大子序列和为16。

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


#define NUM 10

void displayarray(int a[], int n);	//display arrays on screen
int initarray(int *p, int n);	//give random values to the array
int maxsum1(int a[], int n);	//O(n^2)
int maxsum2(int a[], int left, int right);	//O(nlogn)
int maxsum3(int a[], int n);	//O(n)
int max3(int, int, int);		//return the max number of the three

int main(void)
{
	int i, cho;
	int a[NUM];
	initarray(a, NUM);
	displayarray(a, NUM);

	while(1)
	{
		printf("please choose a algroithm\n");
		printf("1. O(n^2)\n");
		printf("2. O(nlogn)\n");
		printf("3. O(n)\n");

		scanf("%d", &cho);

		switch(cho)
		{
			case 1:
				printf("the maxsub id %d\n", maxsum1(a, NUM));
				break;
			case 2:
				printf("the maxsub id %d\n", maxsubsum2(a, NUM));
				break;
			case 3:
				printf("the maxsub id %d\n", maxsum3(a, NUM));
				break;
			default:
				break;

		}
	}

	return 0;
}

int initarray(int *p, int n)
{
	int i;
	srand((int)time(NULL));
	for (i = 0; i < n; i++)
	{
		p[i] = rand() % 20 - 10;
	}
	return 1;
}
void displayarray(int a[], int n)
{
	int i;
	for (i = 0; i < n; ++i)
	{
		printf("%d\t", a[i]);
	}
}

int maxsum1(int a[], int n)
{
	int i, j;
	int tempsum;
	int maxsum = 0;
	for (i = 0; i < n; i++)
	{
		tempsum = 0;
		for (j = i; j < n; j++)
		{
			tempsum += a[j];
			if (tempsum > maxsum)
			{
				maxsum = tempsum;
			}
		}

	}
	return maxsum;
}
int maxsum2(int a[], int left, int right)
{
	int maxleftsum, maxrightsum;
	int maxleftbordersum, maxrightbordersum;
	int leftbordersum, rightbordersum;
	int center, i;

	if (left == right)		//base case
	{
		if (a[left] > 0)
			return a[left];
		else
			return 0;
	}

	center = (left + right) / 2;
	maxleftsum = maxsum2(a, left, center);
	maxrightsum = maxsum2(a, center+1, right);

	maxleftbordersum = 0; leftbordersum = 0;
	for (i = center; i >= left; i--)
	{
		leftbordersum += a[i];
		if (leftbordersum > maxleftbordersum)
			maxleftbordersum = leftbordersum;
	}

	maxrightbordersum = 0; rightbordersum = 0;
	for (i = center + 1; i <= right; i++)
	{
		rightbordersum += a[i];
		if (rightbordersum > maxrightbordersum)
			maxrightbordersum = rightbordersum;
	}

	return max3(maxleftsum, maxrightsum, maxleftbordersum + maxrightbordersum);
}

int maxsum3(int a[], int n)
{
	int i;
	int tempsum, maxsum;
	tempsum = 0;
	maxsum = 0;
	for (i = 0; i < n; i++)
	{
		tempsum += a[i];
		if (tempsum > maxsum)
			maxsum = tempsum;
		if (tempsum < 0)
			tempsum = 0;
	}
	return maxsum;
}

int max3(int a, int b, int c)
{
	int two;
	two = a > b ? a : b;
	return two > c ? two : c;
}
int maxsubsum2(int a[], int n)
{
	return maxsum2(a, 0, n-1);     
}