항 저 우 전기 1003 Max Sum[연속 서브 시퀀스 최대 화]

제목 링크:
http://acm.hdu.edu.cn/showproblem.php?pid=1003
제목:
즉,일련의 데 이 터 를 제공 하여 연속 적 인 하위 서열 의 최대 화 를 구 하 는 것 이다.
문제 풀이 방향:
우 리 는 찾 은 하위 서열 의 최대 값 을 max 로 저장 할 수 있 기 때문에 끊임없이 비교 하여 max 의 값 을 업데이트 하면 마지막 에 우 리 는 가장 큰 하위 서열 의 합 을 얻 을 수 있 기 때문에 폭력 검색 으로 이전 블 로 그 를 만 날 수 있다 는 생각 을 하기 쉽다.이러한 시간 복잡 도 는 O(n^3)로 시간 을 초과 한 것 이다.
또한 하나의 숫자 가 마이너스 가 아니라면 아무리 작 아 도 플러스 가 커지 고 커 질 수 있다 고 생각 하기 때문에 우 리 는 다른 변수 로 곧 추가 할 숫자 가 0 보다 크 든 0 보다 작 든 판단 해 야 한다.0 보다 작 을 때 sum 을 0 으로 돌리 고 다시 판단 해 야 한다.
예 를 들 면 이 예.
-1,5,-3,6,-7 과 가장 큰 하위 서열 은(-1,5,-3,6,-7)이 어야 한다.그 전에 고민 한 것 은 6 을 넣 으 면 멈 춰 야 한다.그러나 이때 sum 은 0 이 아니 라 어떻게 해 야 마지막 최대 치 를 질 수 있 을 까 하 는 생각 이 들 었 다.나중에(-1,5,-3,6)는 max 에 저장 되 었 다.이때 sum 은 0 보다 크 지만-7 을 더 하면 max 보다 작 을 것 이다.그래서 sum 의 값 변 화 는 max 에 영향 을 주지 않 기 때문에 sum 의 값 을 고려 할 필요 가 없습니다.
관건 적 인 점-최대 치 는 항상 max 안에 있 습 니 다.

#include<stdio.h>

int main()

{

	int ncase,a;

	long int num;

	int i;

	while(scanf("%d",&ncase)!=EOF)

	{

		int flag=1;

		while(flag<=ncase)

		{

			int sum=0;

		    int max=-1001;//          -1000 1000  ，   max -1001

		    int beg=0,len=0,end=0;

		    scanf("%ld",&num);

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

			{

			   scanf("%d",&a);

			   sum=sum+a;

			   len++;

			   if(sum>max) //max     

			   {

				beg=len;

				max=sum;

				end=i;

			   }

			    if(sum<0)

			   {

				sum=0;

				len=0;

			   }

			

			}

		

		

		printf("Case %d:
",flag);

		printf("%d %ld %ld
",max,end-beg+1,end);

		

		if(flag!=ncase)

			printf("
");

		flag++;

	}

	}

}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

🏃‍♀️[프로그래머스] 징검다리 건너기

문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

항 저 우 전기 1003 Max Sum[연속 서브 시퀀스 최대 화]

좋은 웹페이지 즐겨찾기