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

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

1912번: 연속합

---

문제 풀이

 연속합을 구하는 문제이기 때문에 경우는 단순하게 2가지 경우로 나뉜다.

1. i번째 더한 값이 최대인 경우

2. i-1번째까지 더한 값보다 i번째 값이 더 큰 경우

배열 DP[i]는 i번째 연속합을 저장한다. DP[i]는 2가지 경우에 따라 DP[i-1] + arr[i]값과 arr[i]값만 비교해주면 된다.

느낀 점

 처음에 DP[i]의 값에 대해서 잘못 생각해서 많이 헤매었다. i번째까지 존재하는 여러 연속합 중에서 최댓값이라고 생각했는데 단순하게 i번째까지의 연속합을 저장하는 것이었다. 문제에서 나온 예를 들면 내가 생각한 것은 DP[2]까지 연속합 중에서 최대인 10이다. 하지만 단순하게 i번째까지의 연속합의 값인 9이다. 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, ans = -1001;
int arr[100001], dp[100001];

int main() {
	cin >> n;
	for (int i = 0; i < n;i++) {
		cin >> arr[i];
	}
	dp[0] = arr[0];
	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);
	}
	for (int i = 0; i < n;i++) {
		ans = max(ans, dp[i]);
	}
	
	cout << ans;
}