글 읽기 - 시간초과..

jhunh 5년 전 0

누적합 배열 hap을 만들어 그것으로 계산하는 코드입니다.

이중for문때문에 시간초과 나는 듯 하는데

더 줄일 수 있는 방법이 있을까요? 아니면 다른 알고리즘을 사용하는 게 좋을까요

#include <stdio.h>
int main()
{
	int n, i, j,arr[100001], hap[100001], ans = 0;
	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
		if(i==0)
			hap[0] = arr[0];
		else
			hap[i] = hap[i - 1] + arr[i];
	}

	for (i = 0; i < n; i++)
		for (j = 0; j < i; j++)
			if (hap[i] - hap[i - j] > ans)
				ans = hap[i]-hap[i-j];

	printf("%d", ans);
}

3587jjh 5년 전 1

다이나믹 프로그래밍으로 풀어보세용

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

문제

문제

출처

ICPC

시간초과..

jhunh 5년 전 0

3587jjh 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말