[dp] 1912 연속합

1912 연속합

 

풀이코드

#include <iostream>
#include <algorithm>

using namespace std;
// 1912 연연속연속합

const int MAX = 100000;

int n;
int A[MAX + 1];
int cache[MAX + 1];

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }
    
    cache[1] = A[1];
    for(int i = 2; i <= n; i++){
        cache[i] = max(A[i], cache[i - 1] + A[i]);
    }
    
    int ans = -123456789;
    
    for(int i = 1; i <= n; i++){
        ans = max(ans, cache[i]);
    }
    cout << ans << '\n';

}

 

해설

---

적용한 레시피 / 방법론 + 접근법

0. 브루트 포스가 불가하다. 100,000 이 n 의 최대이기에 2^100,000... 불가능하다.

1. cache[i] : max(A[i], cache[i - 1] + A[i])

- cache : A[i] 로 끝나는 연속합의 최대를 저장한다.

풀이

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

이전에 풀었던 코드와 비교해보자.