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

void max_sum_left(int *array_num, int n, int *array_sum)
{
	int sum = 0;
	int max_sum = array_num[0];
	array_sum[0] = array_num[0];

	int i;
	for (i = 1; i < n; ++i){
		sum += array_num[i];
		if (max_sum < sum) max_sum = sum;
		if (0 > sum) sum = 0;
		array_sum[i] = max_sum;
	}
};

void max_sum_right(int *array_num, int n, int *array_sum)
{
	int sum = 0;
	int max_sum = array_num[n - 1];
	array_sum[n - 1] = array_num[n - 1];

	int i;
	for (i = n - 2; i > -1; --i){
		sum += array_num[i];
		if (max_sum < sum) max_sum = sum;
		if (0 > sum) sum = 0;
		array_sum[i] = max_sum;
	}
};

int max_sum(int *array_num, int n)
{
	int *array_left = (int *)malloc(sizeof(int) * n);
	int *array_right = (int *)malloc(sizeof(int) * n);

	max_sum_left(array_num, n, array_left);
	max_sum_right(array_num, n, array_right);

	int sum = array_left[0] + array_right[1];
	int max_sum = sum;

	int i;
	for (i = 1; i < n - 1; ++i){
		sum = array_left[i] + array_right[i + 1];
		max_sum = (sum > max_sum) ? sum : max_sum;
	}

	free(array_left);
	free(array_right);
	return max_sum;
};

void loop()
{
	int n;
	scanf("%d", &n);

	int * array_num;
        array_num = (int *) malloc(sizeof(int) * n);

	int i = 0;
	int in;
	while (i < n){
		scanf("%d", &in);
		array_num[i] = in;
		++i;
	}

	printf("%d\n", max_sum(array_num, n));
	free(array_num);
};

int main(void)
{
	int n;
	scanf("%d", &n);

	int i = 0;
	while (i++ < n){
		getchar();
		loop();
	}
	return 0;
};

• Re:为什么总是WrongAnswner? (1810) pcoat 2008-08-06 16:00:15