1912번-연속합

문제

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

1912번: 연속합

---

접근방법

1) 접근 사고

처음에는 이분탐색으로 구현을 할 려고 했었다.

그러나 이분탐색 부분을 구현하던 도중 두 개의 값을 더 한것을 어떻게 표현할 것인지에 대해 막혀서 다시 고민을 했었고

두 개를 더할 것인가 말 것인가에서 DP로 점화식을 세우면 될 것 같다고 생각을 하였다.

2) 시간 복잡도

DP로 구현을 하였으므로 시간초과 관련 문제는 없었다. 자료형도 최대 100,000 * 1000 = 1,000,000,000 이기 때문에 int형으로 사용이 가능하다.

3) 배운 점

DP가 갱신이 되는 순간 한 번도 더 하지 않았다는 의미의 점화식을 사용할 수 있게 되었다.

4) PS

점화식은 언제나 어렵다..

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 1e5 + 1;
 
int n;
 
int main(void)
{
    fastio;
    cin >> n;
 
    vector<int> v(n , 0);
    vector<int> cache(n , 0);
    for(int i = 0; i < n; i++)
        cin >> v[i];
    cache[0] = v[0];
    int ret = cache[0];
 
    for(int i = 1; i < n ; i++)
    {
        cache[i] = max(cache[i - 1] + v[i], v[i]); //cache[i] 값이 갱신되는 순간 아직 더하지 않은 값이다. 즉 한 번 더 더할 수 있는 기회가 있는 것이다.
        ret = max(ret, cache[i]);
    }
    cout << ret << "\n";
 
    return 0;
}