이는 DP응용 문제이다.

먼저 우리는 수열에서 숫자를 빼는 여부가 최적해에 영향을 미친다는 것을 알 수 있다.

이를 통해 정의한다.

dp[i][j] = 수열에서 원소를 j(j=0 or j=1)개 지울 때 수열에서 i번째 수까지의 연속합

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

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

dp배열을 채워주면서 최댓값을 구해주면 된다.

#include <bits/stdc++.h>
#define MEM 100003
#define sanic ios_base::sync_with_stdio(0)
#define MOD 1000000007
using namespace std;
typedef long long lld;
const int INF = 1e9+7;
int n,ans=-INF;
int s[MEM];
int dp[MEM][2];
main(){
    sanic;
    cin >> n;
    for(int i=2; i<n+2; i++)
        cin >> s[i];
    for(int i=2; i<n+2; i++){
        dp[i][0] = max(dp[i-1][0]+s[i], s[i]);
        dp[i][1] = max(dp[i-2][0]+s[i], dp[i-1][1]+s[i]);
        ans = max(dp[i][0], ans);
        ans = max(dp[i][1], ans);
    }
    cout << ans;
}

---