글 읽기 - 연속합 질문입니다.ㅠㅠ 도와주세요

dmsgh7678 8년 전 0

num[]이라는 배열을 만들어 숫자를 집어넣고

dp[]라는 배열을 만들어 dp[i] -> i 번째 중에서 가장 큰 연속합 수

그리고 sum이라는 변수를 통해 음수가 나오면 0으로 초기화 양수일경우 0에 그양수를 더한 값으로 하여 dp[i-1]과 비교하는 식으로 알고리즘을 짰습니다. 그런데 어디가 잘못됬는지 모르겠습니다. ㅠㅠ

도와주세요...

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int *num;
	int *dp;
	int sum=0;
	int i,n;
	scanf("%d",&n);
	num=(int*)malloc(sizeof(int)*n);
	dp=(int*)malloc(sizeof(int)*n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&num[i]);
	}
	dp[0]=num[0];
	if(num[0]>=0)//처음수가 양수 일때
		sum=num[0];
	else// 처음수가 음수일 때
		sum=0;
	
	
	for(i=1;i<n;i++)
	{
		if(num[i]>=0) //양수일 경우
		{
			sum+=num[i];
		}
		else // 음수일 경우
		{
			sum=0;
		}
		if(dp[i-1]>=sum)
		{
			dp[i]=dp[i-1];
		}
		else
		{
			if(num[i]>0)
				dp[i]=sum;
			else// 처음에 음수가 연속으로 나오는 경우
			{
				if(dp[i-1]>=num[i])
					dp[i]=dp[i-1];
				else
					dp[i]=num[i];

			}
		}
	}

	printf("%d",dp[n-1]);
	free(num);
	free(dp);
	return 0;
}

ntopia 8년 전 0

10000 -1 10000

이 데이터는 답이 19999 입니다.. 잘 나오시나요..?

dmsgh7678 8년 전 0

아 그렇군요 음수가 포함되도 큰경우가 있군요.. 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

연속합 질문입니다.ㅠㅠ 도와주세요

dmsgh7678 8년 전 0

ntopia 8년 전 0

dmsgh7678 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말