[C++] BOJ 1912번: 연속합

문제 링크

문제 풀이

해당 문제를 DP(Dynamic Programming) 알고리즘을 이용하여 해결할 수 있다.

dp[i] = dp[i-1] + arr[i], 단 (dp[i-1] + arr[i]) < 0일 경우 dp[i] = 0.

위의 식은 i = 0... n-1에 대하여 arr[i] < 0일 경우엔 성립되지 않음에 주의하자.

코드

#include <bits/stdc++.h>

using namespace std;

int arr[100006];
int n;
int result;
int dp[100006]; // 연속된 수열의 합 중 n번째까지 가장 큰 합

void calcDp()
{
    bool allMinus = true;
    dp[0] = arr[0];
    result = -9999;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > result)
            result = arr[i];
        if (arr[i] > 0)
            allMinus = false;
    }
    if (allMinus)
        return;
    for (int i = 1; i < n; i++)
    {
        dp[i] = dp[i - 1] + arr[i];
        if (dp[i] < 0)
            dp[i] = 0;
        if (result < dp[i])
            result = dp[i];
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    calcDp();

    cout << result << '\n';

    return 0;
}