글 읽기 - 데이터 추가해주세요.

seedkin 4년 전 0

100000

1 -1 1 -1 1 -1 1 -1 1 -1 .....

밑의 코드가 안터지고 패스했어요

시간복잡도는 양수 음수 변경되는 횟수 m에 대해서 O(m^2)입니다.

#include<stdio.h>

int arr[100005] = { 0, };
int sum[100005] = { 0, };

int main() {
	int n;
	int result = -10000;
	scanf("%d", &n);	
	int idx = 0;
	int minus = 0;
	for (int i = 0; i < n; i++) {
		int d;
		scanf("%d", &d);
		if (d > result) result = d;
		if (idx % 2 == 0 && d < 0) {		
			idx++;
		}
		else if (idx % 2 == 1 && d > 0) {
			idx++;
		}	
		arr[idx] += d;
	}
	idx++;

	sum[0] = arr[0];
	if (sum[0] > result && arr[0] != 0) result = sum[0];

	for (int i = 1; i < idx; i++) {
		sum[i] = sum[i - 1] + arr[i];
		if (sum[i] > result) result = sum[i];
	}

	for (int end = 0; end < idx; end++) {
		for (int start = 0; start < end; start++) {
			int s = sum[end];
			s -= sum[start];
			if (s > result) result = s;
		}
	}
	
	printf("%d", result);

	return 0;
}

startlink 4년 전 0

재채점했습니다.

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

문제

문제

출처

ICPC

데이터 추가해주세요.

seedkin 4년 전 0

startlink 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말