백준 1912번: 연속합

[문제 링크]

1912번: 연속합

---

이 문제는 dp 함수를 수행하면서 만들어지는 연속합 중 최대값을 저장해줘야 한다.

 

TopDown 알고리즘은 다음과 같다.

시작 위치가 n일 때 최대 연속합은 시작 위치가 n-1일 때 최대 연속합에 n번째가 가지는 정수를 더한 값과 n번째가 가지는 정수 중 더 큰 값이 최대 연속합이 된다. 따라서 점화식은 다음과 같이 표현할 수 있다. 

 

TopDown(n) = max(TopDown(n-1) + arr[n], arr[n])

 

위 점화식을 이용하여 첫번째부터 마지막까지를 시작 위치로 했을 때 나오는 최대 연속합을 구하면서 그중 최대값을 저장하고 출력하도록 구현하면 된다.

 

BottomUp 알고리즘도 탐색 순서만 다를뿐 TopDown 알고리즘과 동일하다.

---

#include <iostream>
using namespace std;

const int MINF = -987654321;

int arr[100001], memo[100001];

inline int max(int a, int b) { return a > b ? a : b; }

int TopDown(int here)
{
	if (here == 0) return arr[here];

	int& ret = memo[here];
	if (ret != MINF) return ret;

	ret = max(TopDown(here-1) + arr[here], arr[here]);

	return ret;
}

int BottomUp(int n)
{
	int ret;
	ret = memo[0] = arr[0];

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

	return ret;
}

int main(void)
{
	for (int i = 0; i < 100001; i++)
		memo[i] = MINF;
	
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	//Top-Down
	int res = MINF;
	for (int i = 0; i < n; i++)
		res = max(res, TopDown(i));
	cout << "TopDown: " << res << endl;
	
	//Bottom-Up
	cout << "BottomUp: " << BottomUp(n) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 64 day