Exception Handling [AtCoder Beginner Contest 134 C]

https://atcoder.jp/contests/abc134/tasks/abc134_c

前提知識

• 累積和

解説

https://atcoder.jp/contests/abc134/submissions/6478504

ある1要素以外の最大値を取りたいという要望には典型テクがある。
累積和を利用するのだが、先頭からと後尾からの2つを構築する。
lft[i] := A[0]～A[i]までの最大値
rht[i] := A[i]～A[N-1]までの最大値
これを作っておけば、i番目以外の最大値はmax(lft[i - 1], rht[i + 1])となる。
端っこの処理は工夫する必要がある。

int N, A[201010];
int lft[201010], rht[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N) lft[i] = A[i];
    rep(i, 1, N) chmax(lft[i], lft[i - 1]);

    rep(i, 0, N) rht[i] = A[i];
    rrep(i, N - 2, 0) chmax(rht[i], rht[i + 1]);

    rep(i, 0, N) {
        int ans = -1;
        if (0 < i) chmax(ans, lft[i - 1]);
        if (i + 1 < N) chmax(ans, rht[i + 1]);
        printf("%d\n", ans);
    }
}