Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用最简单的o(n2)的算法,为什么是WA呢?

Posted by witshy at 2008-01-31 20:53:33 on Problem 2796
第一次上这里来,没做过题,哪位老大指教一下?

#include "stdio.h"

#define  MAX  100000
int main()
{
	int a[MAX+1];


	int i, j;

	int l, r;
	__int64 maxvalue = 0;

	int min ;
	__int64 sum = 0;
	__int64 value = 0;

	scanf("%d\n", &a[0]);
	for (i=1; i<=a[0]; i++)
		scanf("%d", &a[i]);

	for (i=1; i<=a[0]; i++)
	{
		sum = min = a[i];
		value = sum * min;
		if (value > maxvalue)
		{
			maxvalue = value;
			l = i;
			r = i;
		}

		for (j=i+1; j<=a[0]; j++)
		{
			sum += a[j];
			if (min > a[j]) 
				min = a[j];
			value = sum * min;
			if (value > maxvalue)
			{
				maxvalue = value;
				l = i;
				r = j;
			}
		}
	}

	printf("%I64d\n", maxvalue);
	printf("%d %d", l, r);

	return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator