[백준/C++] 13398번 연속합 2

백준

---

🤔문제 이해

연속된 몇 개의 수를 선택했을 때 그 합이 가장 큰 수열의 합을 출력하는데 그 수열 중에서 하나를 없앨 수 있는 문제이다.

---

💡첫번째 아이디어

하나를 어떻게 없앨까 하다가 바로 전에 푼 가장 긴 바이토닉 부분 수열이 떠올랐다.

앞에서 순서대로 합이 가장 큰 연속합1을 구해주고, 뒤에서 순서대로 합이 가장 큰 연속합2을 구해주고 어느 숫자를 기준으로 양옆으로 연속합1과 2를 더한 값이 가장 크다면 그 기준 숫자를 없앤 것이 더 큰거고, 연속합1의 최댓값이 가장 크다면 하나를 없애지 않아도 가장 큰 연속합을 구할 수 있는 것이라고 생각해서 풀었다. 

 

🔥풀이🔥

dp[i]는 i번째 수를 마지막 수로 했을 때 가장 큰 연속합을 의미한다.

dp2[i]는 i번째 수를 첫번째 수로 했을 때 가장 큰 연속합을 의미한다.

 

1. dp와 dp2를 모두 입력된 수열로 초기화하고, 0번째 dp를 maxInt로 초기화한다.

2. i는 1부터 n-1까지로 dp[i]와 dp[i-1]+arr[i]과 비교해서 더 큰 값을 dp[i]에 넣어주고, maxInt와 dp[i]를 비교해 더 큰 값을 maxInt에 넣어준다.

3. i는 n-2부터 0까지로 dp2[i]와 dp2[i+1]+arr[i]과 비교해서 더 큰 값을 dp2[i]에 넣어주고, maxInt와 dp2[i]를 비교해 더 큰 값을 maxInt에 넣어준다.

4. dp2의 n-1번째 값과 dp2[0]번째 값을 maxInt와 비교해 더 큰 값을 maxInt에 넣어준다.

5. i는 1부터 n-1까지로 i번째 숫자를 제외한 dp[i-1]+dp2[i+1]의 값을 maxInt와 비교해 더 큰 값을 maxInt에 넣어준다.

5. maxInt값 출력!

 

 

❌트러블 슈팅

maxInt를 업데이트해주는 과정이 세세하게 들어가야 했다. 

---

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

long long dp[100001];
long long dp2[100001];
long long arr[100001];
int n;
long long maxInt;

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        dp[i] = arr[i];
        dp2[i] = arr[i];
    }
    maxInt = dp[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(dp[i], dp[i - 1] + arr[i]);
        maxInt = max(maxInt, dp[i]);
    }

    for (int i = n - 2; i >= 0; i--) {
        dp2[i] = max(dp2[i], dp2[i + 1] + arr[i]);
        maxInt = max(maxInt, dp2[i]);
    }
    maxInt = max(maxInt, dp2[n-1]);
    maxInt = max(maxInt, dp2[0]);
    for (int i = 1; i < n; i++) {
        long long tmp = dp[i - 1] + dp2[i + 1];
        if (tmp > maxInt) maxInt = tmp;
    }
    cout << maxInt;

}