글 읽기 - 안되는 경우를 못찾겠어요...

poia0304 6년 전 0

구간 합을 이용해서 풀려고 하는데

구간합중에서 가장 큰 값 - 가장 작은 값을 출력할려고 하는데 자꾸 틀렸다고 나오네요..

테스트 케이스 안되는 걸 알려주시면 감사하겠습니다.ㅠㅠ

#include <iostream>
//#include <cstdio>
#include <algorithm>
#include <climits>

using namespace std;

long long arr[100005];
long long tree[100005];
long long sum[100005];
int n;
long long max(long long a,long long b,long long c) {
	return max(max(a,b),c);
}
void update(int pos, long long data) {
	while (pos <= n) {
		tree[pos] += data;
		pos += (pos & -pos);
	}
}
long long getSum(int pos) {
	long long ret = 0;
	while (pos > 0) {
		ret += tree[pos];
		pos -= (pos&-pos);
	}
	return ret;
}
int main()
{
	cin >> n;
	long long tmp = INT_MIN;
	for (int i = 1; i <= n; ++i) {
		//scanf("%lld", &arr[i]);
		cin >> arr[i];
		update(i, arr[i]);
		tmp = max(tmp,arr[i]);
	}
	int minPos = 0,maxPos = 0;
	long long maxNum = LLONG_MIN, minNum = LLONG_MAX;
	for (int i = 1; i <= n; ++i) {
		sum[i] = getSum(i);
		minNum = min(minNum,sum[i]);
		if (minNum == sum[i]) minPos = i;
		maxNum = max(maxNum,sum[i]);
		if (maxNum == sum[i]) maxPos = i;
	}
	
	if (minPos < maxPos) {
		cout << max(maxNum,tmp,sum[maxPos] - sum[minPos]) << endl;
		return 0;
	}
	else {
		for (int i = minPos+1; i <=n ;++i) {
			maxNum = max(tmp,maxNum,sum[i]-sum[minPos]);
		}
		for (int i = 1; i < maxPos; ++i) {
			maxNum = max(tmp,maxNum,sum[maxPos]-sum[i]);
		}
	}
	
	cout << max(maxNum,tmp) << endl;

	return 0;
}

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

문제

문제

출처

ICPC

안되는 경우를 못찾겠어요...

poia0304 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말