백준 1912번: 연속합(C++)

www.acmicpc.net/problem/1912

1912번: 연속합

코드

#include <iostream>
using namespace std;

int n;
int arr[100000];
int dp[100000];

void init(){
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> arr[i];
	}
}

void solve(){
	dp[0] = arr[0];
	int max_num = dp[0];
	for(int i=1; i<n; i++){
		dp[i] = dp[i-1] + arr[i] > arr[i] ? dp[i-1] + arr[i] : arr[i];
		max_num = dp[i] > max_num ? dp[i] : max_num;
	}
	cout << max_num;
}
int main() {
	init();
	solve();
}

풀이

DP[i] = max(DP[i-1] + arr[i], arr[i])

위 점화식을 토대로 풀면 바로 풀리는 문제입니다.

연속되는 수 중간에 음수가 있다 하더라도 연결되어있는 다른 수가 크다면

충분히 메꿀수 있다는 것을 생각하시면 됩니다.