#include<iostream.h>
#include<stdio.h>
#define Min	-10001 
#define Max	10001
int NEG_INF = 0x80000000;
int POS_INF = 0x7fffffff;
int a[5001];//数据
int b[5001];//记录正负值
int x[5001];//当前最优路径
int r[5001];//当前路径

int MaxSumWithR(int * a, int n)
{
	int i,j;

	for(j=1;j<=n;j++)
	{
		r[j]=0;
		x[j]=0;
	}
	int sum=0;
	int s=0;
	for(i=1;i<=n;i++)
	{
		if(s>0)
		{
			s+=a[i];
			r[i]=1;
		}
		else//s<=0
		{
			s=a[i];
			for(j=1;j<=n;j++)
				r[j]=0;
			r[i]=1;
		}
		if(sum<s)
		{
			sum=s;
			for(j=1;j<=n;j++)
				x[j]=r[j];
		}
	}
	return sum;
}

int MaxSum(int * a, int begin, int end)//求a[begin...end]的最大和
{
	int n=end-begin+1;
	int i;
	int s=0;
	int sum=NEG_INF;
	for(i=begin;i<=end;i++)
	{
		if(s>0)
		{
			s+=a[i];
		}
		else//s<=0
		{
			s=a[i];
		}
		if(sum<s)
		{
			sum=s;
		}
	}
	return sum;
}

int MaxNum(int s1,int s2, int s3)
{
	int s4 = s1>s2 ? s1:s2;
	int s = s4>s3? s4:s3;
	return s;
}

int main()
{
//	cout<<NEG_INF<<endl;
	int i,k,times;
	int T;
	scanf("%d",&T);

	printf("\n");
	for(times=1;times<=T;times++)
	{

		int sum=0;
		int N;
		cin>>N;
		for(i=1;i<=N;i++)
		{
			scanf("%d",&a[i]);
			if(a[i]>0)
			{
				b[i]=1;//正数表示为1,0或负数表示为0
			}
		}
		int IsAllPositive=0;
		int IsAllNegative=0;
		int pos_count=0;
		int neg_count=0;
		for(i=1;i<=N;i++)
		{
			if(b[i]==1)
				pos_count++;
			else
				neg_count++;
		}
		if(pos_count==N)//全部是正数
		{
			for(i=1;i<=N;i++)
				sum+=a[i];
			printf("%d\n\n", sum);
		}

		else if(neg_count==N)//全部是负数
		{
			int s1=Min;
			int t1=0;
			int s2=Min;
			for(i=1;i<=N;i++)
			{
				if(a[i]>s1)
				{
					s1=a[i];
					t1=i;
				}
			}
			for(i=1;i<=N;i++)
			{
				if(a[i]>s2 && i!=t1)
				{
					s2=a[i];
				}
			}
			sum=s1+s2;
			printf("%d\n\n", sum);
		}

		else//正负数都有
		{
			int sum1=MaxSumWithR(a,N);//x[i]==0的为未访问的
			k=0;
			int begin1;//最大子串的开始位置
			int end1;//最大子串的结串位置
			for(i=1;i<=N;i++)
			{
				if(x[i]==1)
				{
					if(k==0)
					{
						begin1=i;
					}
					k++;
				}
			}
			end1=begin1+k-1;
//			cout<<"begin1:"<<begin1<<endl;
//			cout<<"end1:"<<end1<<endl;
			if(begin1==end1)//只有一个正数的情况,即最大子串只有一个元素
			{
				int max=Min;
				for(i=1;i<=N;i++)
				{
					if(i!=begin1 && a[i]>max)
						max=a[i];
				}
				sum=sum1+max;
				printf("%d\n\n", sum);
			}
			else
			{
				int sum2=NEG_INF;
				int sum3=NEG_INF;
				int sum4=0;
				if(begin1!=1)
				{
					sum2=MaxSum(a,1,begin1-1);
				}
				if(end1!=N)
				{
					sum3=MaxSum(a,end1+1,N);
				}
				for(i=begin1;i<=end1;i++)//找出最小的负数
				{
					if(a[i]<sum4)
						sum4=a[i];
				}
				sum4=-sum4;
//				cout<<"sum1:"<<sum1<<endl;
//				cout<<"sum2:"<<sum2<<endl;
//				cout<<"sum3:"<<sum3<<endl;
//				cout<<"sum4:"<<sum4<<endl;
				int sum5=MaxNum(sum2, sum3, sum4);
				sum=sum1+sum5;
				printf("%d\n\n", sum);
//				cout<<"sum5:"<<sum5<<endl;
//				cout<<"sum :"<<sum<<endl;
			}
		}

	}//for
	return 0;
}

• Re:我的程序RUNTIME ERROR,是什么回事?Runtime Error是什么原因造成的? (3463) 7412580 2010-08-11 11:16:32
  • Re:我的程序RUNTIME ERROR,是什么回事?Runtime Error是什么原因造成的? (26) applepi 2010-08-23 12:49:53