CS Academy Subarray Removal

リンク : https://csacademy.com/contest/archive/task/subarray_removal/submissions/

問題概要

長さNの数列が与えられる。この数列から空でないかつ最大N-1個の連続した数列を取り除く。そのときの区間の和が最大のときの値を求めよ。

解説

まず、5つの区間に分けられる。(全部取らない)→(全部取る)→(取り除かれる)→(全部取る)→(全部取らない)　となる。これに対応するようにdp[i][j]をつくるとできる。(j=0のとき取らない、j=1のとき取る...)
「空」でない数列を取り除くを読めなくてごめんなさい。
あと類題として、 atcoder.jp
がある。

LL n, a[110000], ans = -INF , dp[110000][3];
int main() {
    cin >> n;
    rep(i, n) {
        cin >> a[i];
    }
    rep(i, n + 1)rep(j, 3)dp[i][j] = -INF;
    //0:排除区間でない、1:排除区間、2:排除区間でない
    rep(i, n) {
        dp[i + 1][0] = max({ dp[i + 1][0],dp[i][0] + a[i],a[i] });
        dp[i + 1][1] = max({ dp[i + 1][1],dp[i][1],dp[i][0] });
        dp[i + 1][2] = max({ dp[i + 1][2],dp[i][2] + a[i],dp[i][1] + a[i] });
    }
    for(int i=1;i<=n;i++)for(int j=1;j<3;j++)ans = max(ans, dp[i][j]);
    cout << ans << endl;
    return 0;
}