BOJ 1912 - 연속합(C++)

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

1912번: 연속합

 

풀이

연속된 수에 대한 최대값이기 때문에 2가지만 고려함

1. 연속하지 않을 때

  - 이전 값과 연속할 때 현재 값보다 작은 경우, 자기 자신을 가지고 감

  - dp[i] > (dp[i-1] + dp[i])

2. 연속할 때

  - 이전 값과 연속할 때 현재 값보다 큰 경우, 연속합을 가지고 감

  - dp[i] < (dp[i-1] + dp[i])

 

순서대로 탐색하며 1, 2를 적용하고 최대값을 갱신 

 

#include <iostream>
#include <algorithm>

#define MIN -987654321

using namespace std;

int dp[100001];

int main() {
    int N;
    int answer = MIN;
    
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> dp[i];
    }
    
    dp[0] = MIN;
    for (int i = 1; i <= N; i++) {
        dp[i] = max(dp[i], dp[i - 1] + dp[i]);
        answer = answer < dp[i] ? dp[i] : answer;
    }

    cout << answer;

    return 0;
}