1912 - 연속합

문제

코드

#include<bits/stdc++.h>
using namespace std;

int dp[100004];
int n,ret;
int a[100004];

int main(){
	ret = -1e9;
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		 cin >> a[i];
	}
	dp[0] = a[0];
	
	for(int i = 1; i <= n; i++){
		dp[i] = max(a[i], dp[i-1] + a[i]);
		ret = max(dp[i], ret);
	}
	cout << ret << '\n';
}

풀이

여기서 dp 배열은 해당 인덱스에서 가질 수 있는 연속된 최대 값을 의미한다.
비교하는 값은 이전까지의 합에 본인 인덱스를 더했을 때 더 크다면 dp[i-1] + a[i] 값이 더 큰 값이 되겠고 아니라면 a[i] 값이 더 큰 값이 될 것이다.
입력 배열의 첫 번째 값을 dp[0]으로 설정한다.
그 후 dp[i] = max(a[i], dp[i-1]+a[i])로 각 상황마다 큰 값을 가지는 배열을 만든 후에 배열의 최대 값을 출력하면 된다.

결과

후기

조금만 생각해보면 금방 풀 수 있었던 dp 문제라고 생각한다.