백준 13398번 연속합 2 (C++)

문제 링크 : www.acmicpc.net/problem/13398

13398번: 연속합 2

이 문제는 백준 11054번 가장 긴 바이토닉 부분 수열을 응용해서 풀 수있다.

 

각 숫자들을 지웠을 경우에 발생하는 최대값을 어떻게 도출하냐가 문제인데, 이를 위해 아래 3가지 배열을 생성한다.

(1) 입력값 (2) i번째에서 끝나는 수열 (3) i번째에서 시작하는 수열

 

우리는 위의 (2)와 (3)을 통해, 최대값을 다음 두 케이스 중 하나로 도출해낼수 있다.

i번째까지의 최대합 vs i-1번째까지 최대합과 i+1번째까지 최대합 (=i를 지웠을때 발생하는 최대값)

 

기본 로직은 연속합의 로직과 동일하므로, 상세한 설명은 생략한다.

 

#include <iostream>
#define MAX 100001
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, ans = -1e9, arr[MAX], dp1[MAX], dp2[MAX];
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
        dp1[i] = arr[i];
        dp2[i] = arr[i];
    }
    for(int i=2; i<=n; i++) dp1[i] = max(arr[i],arr[i]+dp1[i-1]); // i에서 끝나는 수열
    for(int i=n-1; i>=1; i--) dp2[i] = max(arr[i],arr[i]+dp2[i+1]); // i에서 시작하는 수열
    for(int i=1; i<=n; i++){
        ans = max(ans,dp1[i]);
        if(i>=2&&i<=n-1)ans = max(ans,dp1[i-1]+dp2[i+1]); // if문 주의
    }
    cout << ans << "\n";
    return 0;
}

if문 주의를 적어놓은 부분을 간과할 경우, 아래와 같은 테스트 케이스에서 오답을 겪을 수 있다.

1
-1
Correct : -1
Fail : 0