[백준] 1912번: 연속합

문제링크 : https://www.acmicpc.net/problem/1912

 

문제풀이

동적 계획법으로 쉽게 풀 수 있는 문제이다.

dp배열을 따로 만들어서, 각 자리까지의 최댓값을 저장한다.

 

소스코드

/*
 * 백준 1912번: 연속합
 */

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 100001

int arr[MAX];
int dp[MAX];

int main() {
	int n;
	cin >> n;

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

	dp[0] = arr[0];

	int max_sum = arr[0];
	for (int i = 1; i < n; i++) {
    	// (현재 값, 현재 값 + 이전까지의 최댓값) 중 더 큰 값 저장
		dp[i] = max(arr[i], arr[i] + dp[i - 1]);
		if (dp[i] > max_sum) max_sum = dp[i];
	}

	cout << max_sum;

	return 0;
}