HDOJ1003 - Max Sum

4915 단어 max
제목의 대의: 1231과 마찬가지로 최대 연속 서열과, 단지 이 제목은 최대 연속 서열과 첫 번째 원소의 위치와 끝 원소의 위치를 요구하는 것이다.
문제풀이: 1231 코드를 그냥 조금만 수정하면 돼요...
#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define MAXN 100005

typedef struct

{

    long x,y;

} NODE;

NODE path[MAXN];

long d[MAXN],a[MAXN];

int main(void)

{

    long i,n,maxs,l,r,T,p;

    scanf("%ld",&T);

    p=1;

    while(T--)

    {

        scanf("%ld",&n);

        for(i=0; i<n; i++)

            scanf("%ld",&a[i]);

        memset(d,0,sizeof(d));

        d[0]=a[0];

        maxs=d[0];

        l=0;

        r=0;

        for(i=1; i<n; i++)

        {

            if(d[i-1]<0)

            {

                d[i]=a[i];

                path[i].x=i;

                path[i].y=i;

                if(d[i]>maxs)

                {

                    maxs=d[i];

                    l=i;

                    r=i;

                }

            }

            else

            {

                d[i]=d[i-1]+a[i];

                path[i].x=path[i-1].x;

                path[i].y=i;

                if(d[i]>maxs)

                {

                    maxs=d[i];

                    l=path[i].x;

                    r=path[i].y;

                }

            }



        }

        printf("Case %ld:
",p++); printf("%ld %ld %ld
",maxs,l+1,r+1); if(T) printf("
"); } return 0; }

좋은 웹페이지 즐겨찾기