글 읽기 - 연속합 반례를 모르겠습니다.

chanmin4 4년 전 0

다이나믹 프로그래밍으로 짯는데... 바로 틀렸습니다가 나오더군요.. 반례좀 알려주시면 감사드리겠습니다 ㅠ

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#define fup(i,a,b,c) for(int i=a;i<=b;i+=c)
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
int n;
vector<long long>arr;
vector<long long>b;
long long maxi = 0;
int check = 0;
int dp() {
	if (arr[0] >= 0) {
		b[0] = arr[0];
		check++;
	}
	for (int i = 1; i <n; i++) {
		if (arr[i] >= 0) {
			b[i] = b[i - 1] + arr[i];
			maxi = max(maxi, b[i]);
			check++;
		}
	}
	if (check == 0) {
		return  *max_element(arr.begin(), arr.end());
	}
	else {
		return maxi;
	}
}
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> n;
	b.resize(n + 1);
	arr.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	cout << dp();
}

tjdwo5313 4년 전 1

input

2 -1 3

output

chanmin4 4년 전 0

2 -1 3 을했을때 출력이 4가나온다는 이야기신가요?

전 output 이 3으로 나오는데 어떻게된건지..

tjdwo5313 4년 전 2

연속합 문제는 연속된 수열의 합을 최대로 해야합니다.

즉 위의 입력

2 -1 3

에 대해서 연속합이 최대가 되는 경우는

3 하나만 선택하는 경우가 아니라 (2, -1, 3)을 모두 선택하는 경우입니다.

즉 답은 4가 되어야 합니다.

chanmin4 4년 전 1

그렇군요 감사합니다!

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

문제

문제

출처

ICPC

연속합 반례를 모르겠습니다.

chanmin4 4년 전 0

tjdwo5313 4년 전 1

chanmin4 4년 전 0

tjdwo5313 4년 전 2

chanmin4 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말