BaekJoon 1912번: 연속합

풀이법

1) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다.

    메모이제이션을 활용하여 현재까지의 최대 합을 구하고 이를 ret이라는 변수에 담아 최대를 반환하게 했다.

    max(직전까지 최대 합+ 현재 값, 현재 값)

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int c[100001];
int d[100001];
int res = -100000000;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		c[i] = a;
	}
	d[0] = c[0];
	for (int i = 1; i < n; i++)
	{
		d[i] = max(d[i - 1] + c[i], c[i]);
		res = max(d[i], res);
	}
	res = max(d[0], res);
	cout << res;
}

github.com/pearlcrum/CodingTest/tree/main