1912 연속합

www.acmicpc.net/problem/1912

1912번: 연속합

고민을 많이 한 문제였는데, 놓친 부분은 다음과 같다.

1. 부분합이 음수가 될 수 있음

2. 부분합 < 0이면, 현재 원소가 가장 큰 부분합

점화식을 세우는게 어렵구나.. 추론이 부족한듯하다.

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100001] = { 0, };
int dp[100001] = { 0, };
int N;
int main()
{
	int result = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	dp[0] = arr[0];
	result = dp[0];

	for (int i = 1; i < N; i++) {
		dp[i] = max(dp[i - 1] + arr[i], arr[i]);
		result = max(dp[i], result);
	}
	printf("%d\n", result);
	return 0;
}