Coding_Test_C++
BaekJoon 1912번: 연속합
펄크럼
2021. 4. 18. 11:24
풀이법
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;
}