[algorithm] 백준 - 연속합 2

이 문제는 DP 문제이다.

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

2. 수열에서 수를 하나 제거할 수 있다.

 

수를 제거했을 경우, 수를 제거 하지 않았을 경우로 나누어서 계산한다.

 

만약 수를 제거 했다면,

현재 위치한 수를 합산하지 않는다면, 여태까지 수열 중 제거한 적이 없는 값

합산한다면 제거한 적이 있는 값

을 비교해서 큰 값을 누적한다. 

 

dp[i][1] = max(arr[i] + dp[i - 1][1], dp[i - 1][0]);

 

수를 제거하지 않는다면,

현재 위치한 수와 수열 중 제거한 적이 없는 값을 비교해서 큰 값을 누적한다.

 

dp[i][0] = max(arr[i] + dp[i - 1][0], arr[i]);

 

따라서 이런 식으로 코드를 작성했다.

 

// 연속합(2)
#include <iostream>
using namespace std;

int main(void){
    int n, arr[100001], dp[100001][2], answer;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    dp[0][0] = arr[0];
    dp[0][1] = 0;
    answer = dp[0][0];
    for(int i = 1; i < n; i++){
        dp[i][0] = max(arr[i] + dp[i - 1][0], arr[i]);
        dp[i][1] = max(arr[i] + dp[i - 1][1], dp[i - 1][0]);
        answer = max(answer, max(dp[i][0], dp[i][1]));
    }
    cout << answer;
}