[BOJ]13398번: 연속합 2(c++)

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

13398번: 연속합 2

 

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // 입력
    int n;
    cin >> n;
    vector<int> input(n + 2);    // 양 끝에 1칸씩 여유를 둔다. 
    for (int i = 1; i <= n; i++)
    {
        cin >> input[i];
    }
 
    /*
        DL[i] : 왼쪽에서부터 i에서의 최대 연속합
        DR[i] : 오른쪽에서부터 i에서의 최대 연속합
    */
    vector<int> DL(n + 2);
    vector<int> DR(n + 2);
    for (int i = 1; i <= n; i++)
    {
        DL[i] = input[i];
        DR[n - i + 1] = input[n - i + 1];
 
        if (DL[i - 1] >= 0)
        {
            DL[i] += DL[i - 1];
        }
        if (DR[n - i + 2] >= 0)
        {
            DR[n - i + 1] += DR[n - i + 2];
        }
    }
 
    // 수를 제거하지 않았을 때 최대값 구하기
    // 수는 반드시 한개 이상 선택해야 하기 때문에 초기값 = DL[1]
    int max = DL[1];
    for (int i = 2; i <= n; i++)
    {
        if (max < DL[i])
        {
            max = DL[i];
        }
    }
 
    /*
        수를 제거했을 때 최대값 구하기
 
        i번째 수를 제거했을 때, i번째 수가 포함되는 최대 연속합
        --> DL[i - 1] + DR[i + 1]
    */
    for (int i = 2; i <= n; i++)
    {
        if (max < DL[i - 1] + DR[i + 1])
        {
            max = DL[i - 1] + DR[i + 1];
        }
    }
    cout << max;
 
    return 0;
}

 

 

TIP1

시간초과를 신경 써주어야 한다!!

// O(n^2)로 풀려다가 시간 초과가 났다..
vector<int> max_sum(n + 2);
int max = 0;
for (int i = 1; i < n + 2; i++)
{
    for (int j = 2; j < n + 2; j++)
    {
        if (j == i)
        {
            continue;
        }
 
        max_sum[j] = input[j];
        int bf_idx = (j - 1 == i) ? j - 2 : j - 1;
 
        if (max_sum[bf_idx] >= 0)
        {
            max_sum[j] += max_sum[bf_idx];
        }
 
        max = (max < max_sum[j]) ? max_sum[j] : max;
    }
}
cout << max;

 

포문을 2번 돌리는 것 보다,

왼쪽/오른쪽 양 끝에서부터 시작하는 배열을 활용하는게 시간효율적이다. O(n)

가장 긴 바이토닉 부분수열 문제 참고

 

TIP2

단, 수는 한 개 이상 선택해야 한다.

문제의 조건을 상세히 읽자!

이것때문에 한참 헤맸다.

 

유용했던 반례

1
-1
답 -1

3
-1 -1 1
답 1