[C++] 백준 1912번: 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

오답 풀이

먼저, 누적합 배열을 계산했다.

그리고 누적합 배열에서 최소값과 최대값을 찾았다.

최소값보다 뒤에 있는 요소 중에 최대값을 찾고,

최대값보다 앞에 있는 요소 중에 최소값을 찾았다.

그리고 그 두 경우에서의 차 중 큰 값을 답으로 출력했다.

그리고 틀렸다.

정답 풀이

https://sihyungyou.github.io/baekjoon-1912/

백준 1912번 : 연속합

위 풀이를 봤다. 음...

https://guiyum.tistory.com/16

C++ 백준 1912번

위 풀이도 봤다. 지난 학기 알고리즘 수업 시간에 다뤘던 유형이다.

매우 대표적인 DP 문제이므로 잘 기억해둬야겠다.

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, N)	for(int i = 0; i < N; ++i)
#define TC(T)		int T; cin >> T; while(T--)
#define FAST_IO		cin.tie(NULL); ios::sync_with_stdio(false);
#define ERR			1e-13
#define EL			"\n"
#define VI			vector<int>
#define VVI			vector<VI>
#define VVVI		vector<VVI>
#define VP			vector<pair<int, int>>
#define VVP			vector<VP>
#define VC			vector<char>
#define VVC			vector<VC>
#define VB			vector<bool>
#define VVB			vector<VB>
#define VVVB		vector<VVB>

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N;
	cin >> N;
	VI seq(N);
	FOR(i, N)
		cin >> seq[i];

	VI DP(N);
	DP[0] = seq[0];
	for (int i = 1; i < N; i++) {
		DP[i] = DP[i - 1] + seq[i];
		if (DP[i] < seq[i])
			DP[i] = seq[i];
	}

	cout << *max_element(DP.begin(), DP.end()) << EL;

	return 0;
}