[백준] 알고리즘 1912번 - 연속합 문제

#include<bits/stdc++.h>
using namespace std;
int dp[100001];
int arr[100001];
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	dp[1] = arr[1];
	int ans = dp[1];
	for (int i = 2; i <= n; i++) {
		dp[i] =arr[i];
		if (dp[i-1]+dp[i]>dp[i]) {
			dp[i] += dp[i - 1];	
		}
		ans = max(ans, dp[i]);
	}
	cout << ans;
	 
}

dp에는 dp[i]=i 번째까지 연속된 수열의 합이 저장된다.

• 즉 dp[i-1]+dp[i]>dp[i] 보다 크게되면 연속적으로 수열의 합에 참여시킨다.
• 만약 dp[i]가 더 크다면 새로운 수열의 합의 시작점이 된다.

최대값을 출력해야 하므로, ans에 최대값을 저장하고 마지막으로 출력한다.