글 읽기 - 시간초과를 어떻게 해야할까요?

bangbadak 4년 전 0

1번째 배열 값부터 n까지 배열 값을 arr에 다 저장시켜놓고 그 후 연산해서 최댓값을 구하는 겁니다. (ex)arr[7] - arr[5] = -14 - 15 (따라서 최댓값 x)

근데 밑에 걸 실행했을 때는 바로 시간초과가 뜨는데 어떻게 처리해야 될까요?

#include<iostream>
#include<algorithm>
using namespace std;
int arr[100002], input[100002], i, j, N, sum, m = -1000;
int main(void)
{
	cin >> N;
	for (i = 1; i <= N; i++)
	{
		cin >> input[i];
		sum += input[i];
		arr[i] = sum;
	}
	for (i = 0, sum = 0; i <= N; i++)
		for (j = i + 1; j <= N; j++)
			if (arr[j] - arr[i] > m)
				m = arr[j] - arr[i];
	cout << m;
}

djm03178 4년 전 1

질문을 올리기 전에 질문 검색을 해보시면 이 문제를 O(N^2)으로 풀면 안 된다는 글이 아주 아주 아주 많습니다.

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

문제

문제

출처

ICPC

시간초과를 어떻게 해야할까요?

bangbadak 4년 전 0

djm03178 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말