[백준 1912번] 연속합

풀이

---

모든 경우의 수를 돌리면 시간초과가 나게된다..

이 문제도 DP를 통해서 구현할 수 있다.

(현재값 + DP이전값) 과 (현재값) 중 큰값을 DP배열에 저장해주면서 Max값이랑 비교한다.

dp[i] = Max(num[i], dp[i - 1] + num[i]);

문제를 해석할 때 놓치는 부분이 있을 수 있다.

입력범위는 -1000 ~ 1000 까지라 int형 내에서 입력을 받을 수 있다.

하지만 입력의 갯수가 n(1≤n≤100,000) 이므로 1000이 연속해서 100000개가 들어와서 DP배열에 쌓게 되면 int형을 벗어날 수 있다.

소스코드

---

#include <iostream>
using namespace std;
 
long long Max(long long a, long long b) {
    return a > b ? a : b;
}
 
int main() {
    int n, num[100001];
    long long dp[100001];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }
    dp[0] = num[0];
    long long Max_val = dp[0];
    for (int i = 1; i < n; i++) {
        dp[i] = Max(num[i], dp[i - 1] + num[i]);    
        if (dp[i] > Max_val) {
            Max_val = dp[i];
        }
    }
    cout << Max_val << '\n';
    return 0;
}