[백준/C++] 1912번: 연속합

문제

https://www.acmicpc.net/problem/1912

1912번: 연속합

---

문제 요약

n개의 정수로 이루어진 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 출력한다.

 

단, 수는 한 개 이상 선택해야 한다.

---

코드

#include <iostream>

#define MAX 100000

using namespace std;

int n;

int arr[MAX];
int dp[MAX]; // dp[i]: i번째 수를 포함하면서, i번째 수까지 수열 중 최대 합

int main() {
	cin >> n;

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

	dp[0] = arr[0];

	int res = arr[0];

	for (int i = 1; i < n; i++) {
		dp[i] = max(arr[i], dp[i - 1] + arr[i]);
		res = max(dp[i], res);
	}

	cout << res;

}

---

코드 설명

Bottom - Up 방식의 Dynamic Programming으로 문제를 해결한다.

 

dp[i]는 주어진 수열에서 i번째 수를 마지막 숫자로 하는 부분 수열 중 합이 가장 큰 수열의 합을 저장한다.

 

dp[i]는

i - 1번째 수를 마지막 숫자로 하는 부분 수열 중 합이 가장 큰 수열에서 i번째 수를 더한 값

과

i번째 수의 값

을 비교해서 더 큰 값이 된다.

 

dp[i]를 구할 때마다 최대값(res)을 갱신하고, 모든 dp테이블을 채우면 최대값을 출력한다.