[BOJ / DP] 13398 연속합 2

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

13398번: 연속합 2

 

13398 연속합 2

알고리즘 : 누적합 / DP

일단 연속합의 최대를 구하는 sum을 이용해 연속합1 의 답을 구해준 뒤,

                        - dp[0][i]에는 배열의 앞에서부터 i번째까지의 최대연속합

                        - dp[1][i]에는 배열의 뒤에서부터 i번째까지의 최대연속합

을 구해줍니다. 그 뒤, 1~n까지 돌며 dp[0][k-1] + dp[1][k+1]로 k번째 수를 제외하였을 때 연속합의 최대를 갱신해 답을 구해줍니다.

 

 

 

 

 

 

 

 

< CODE >

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100005];
int dp[2][100005];

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, result = -987654321, msum = 0, nResult = -987654321;

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        
        if (msum < 0)
            msum = arr[i];
        else
            msum += arr[i];

        nResult = max(nResult, msum);
    }

    dp[0][0] = dp[1][0] = dp[0][n + 1] = dp[1][n + 1] = -987654321;

    for (int i = 1; i <= n; i++)
    {
        dp[0][i] = arr[i];

        if (dp[0][i - 1] > 0)
            dp[0][i] += dp[0][i - 1];

        int j = n - i + 1;

        dp[1][j] = arr[j];

        if (dp[1][j + 1] > 0)
            dp[1][j] += dp[1][j + 1];
    }

    result = nResult;

    for (int i = 1; i <= n; i++)
        result = max(result,dp[0][i - 1] + dp[1][i + 1]);

    cout << result << '\n';

    return 0;
}

시간 : 8ms

 

태그 : #BOJ 연속합 #BOJ 연속합2 #백준 연속합2 #13398 연속합