🖊️ 문제

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

---

🖊️ 풀이

DP문제는,. 코드가 굉장히 간단하다.

연속하는 수의 합이 최대여야 하므로,
i번째 수 까지의 합의 최대값들을 저장한다.

i번째 수의 합의 최댓값은
1. 연속할 때 -> 이전까지의 합의 최댓값 + 현재값
2. 비연속 -> 현재값 (연속끊김)

연속할 때의 경우.. 이전 값을 고려하지 않으려면 걍 현재까지의 최댓값을 저장해주면 된다.
그래서 0번째부터 냅다 해주면 아래처럼 된다.

#include <iostream>
using namespace std;

int n;
int arr[100'001];
int dp[100'001];

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]);
	}

	int result = -1000 * n;
	for (int i = 0; i < n; i++) {
		result = max(result, dp[i]);
	}
	
	cout << result << endl;
}