1003n.c

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1003 Max Sum
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 1024 K  
GUN C

input 4 -6 -8 0 -3
output 0 3 3
*/
#include <stdio.h>
#include <stdlib.h>
#define T 20
#define N 100000

int main()
{
	int t,n,ca,cb,now,add,sub,flag,start,end,p1,p2;
	int num[N]={0};
	if(scanf("%d",&t)==1)
	{
		if(t>T)
			return 0;
		for(ca=0;ca<t;ca++)
		{
            printf("Case %d:\n",ca+1);
			scanf("%d",&n);
			p1=p2=start=end=flag=now=add=sub=0;
			for(cb=1;cb<=n;cb++)
			{
				scanf("%d",&num[cb]);
                switch(flag)
                {
                case 0:
                    if(num[cb]>=0)
                    {
                        now+=num[cb];
                        end=cb;
                        if(start==0)
                            start=cb;
                    }
                    else
                    {
                        if(end!=0)
                        {   flag=1;p1=cb;sub=num[cb];}
                    }
                    break;
                case 1:
                    if(num[cb]>=0)
                    {
                        flag=2;p2=cb;
                        add=num[cb];
                    }
                    else
                    {
                        sub+=num[cb];
                    }
                    break;
                case 2:
                    if(num[cb]>=0)
                    {
                        add+=num[cb];
                    }
                    else
                    {
                        if(add+sub+now<add)
                        {
                            start=p2-1;
                            end=cb-1;
                            now=add;
                            sub=add=0;
                        }
                        else
                        {
                            if(add+sub>0)
                            {
                                end=cb-1;
                                now+=add+sub;
                                sub=add=0;
                            }
                            else
                            {   end=p1-1;}
                        }
                        flag=1;
                        sub=num[cb];
                        p1=cb;
                    }
                    break;
                }	
            }
			if(flag==0 && end==0)
                for(cb=1,start=end=1;cb<=n;cb++)
                {
                    if(num[cb]>num[start])
                    {   end=start=cb;now=num[start];}
                }
			
			printf("%d %d %d\n",now,start,end);
			if(ca!=t-1)
                printf("\n");
		}		
	}	
	return 0;
}