[DP] BOJ 13398 연속합 2 (C++)

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

13398번: 연속합 2

 

문제 해결 알고리즘

 

한 칸 넘은 경우와 넘지 않은 경우 두 가지 배열을 다이나믹 프로그래밍을 한다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100001;
int arr[MAX], dp[MAX][2];

int main(){
    int n; cin >> n;

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

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

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

    cout << result;
}