CodeChef Better Maximal Sum - mayoko’s diary

これが一番難しかったです。

問題

数列 a の maximal sum とは, 空でない a の連続した数列の要素の和のうち, 最も大きいものである。数列 a の要素を最大 1 個取り除いてよいとき, a の maximal sum を求めよ。

解法

まず基本的な問題なんですが, a の要素を 1 つ取り除く, という設定がない場合どう解くかを考えます。区間 [l, r) の和は, 累積和 sum を使って,
sum[r] - sum[l]
と書くことができます。よって, r を固定した場合, その最大値は, sum[l] が最小の場合に実現できます。これは r を順番に見ていくような形にしていくことで O(N) で処理できますね。

今回の問題では上のアルゴリズムを少し変更して解きます。

数列から要素を一つも取り除かない場合は先ほどと同じです。取り除く場合は,
[l, i) の区間和 + [i+1, r) の区間和
という形になります。

[l, i) の区間では今まで通り sum[l] の最小値を探せば良さそうです。また, [i+1, r) の区間では, [i+1, N] の区間にある r について sum[r] の最大値を探せば sum[r]-sum[i+1] の最大値を求められます。

ということで, 今回の問題の場合は,

sum[r] = [r, N] の区間における sum[i] の最大値を前処理で計算しておけば答えを求められます。

正答率が異様に低かったので愚直解と多少比べてから提出しました。

const ll INF = 1ll<<55;

ll solve(std::vector<int> v) {
    int N = v.size();
    vector<ll> sum(N+1), maxi(N+1);
    for (int i = 0; i < N; i++) {
        sum[i+1] = sum[i]+v[i];
    }
    maxi[N] = sum[N];
    for (int i = N-1; i >= 0; i--) {
        maxi[i] = max(maxi[i+1], sum[i]);
    }
    ll ret = -INF;
    ll miniSum = 0;
    for (int i = 1; i <= N; i++) {
        ret = max(ret, sum[i]-miniSum);
        if (i < N) {
            ret = max(ret, sum[i]-miniSum + (maxi[i+1]-sum[i+1]));
        }
        miniSum = min(miniSum, sum[i]);
    }
    return ret;
}

// O(N^3)
ll naive(std::vector<int> v) {
    int N = v.size();
    std::vector<ll> sum(N+1);
    for (int i = 0; i < N; i++)
        sum[i+1] = sum[i]+v[i];
    ll ret = -INF;
    for (int l = 0; l < N; l++) for (int r = l+1; r <= N; r++) {
        ret = max(ret, sum[r]-sum[l]);
        if (r-l > 1) {
            for (int m = l; m < r; m++) {
                ret = max(ret, sum[r]-sum[l]-v[m]);
            }
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        std::vector<int> v(N);
        for (int i = 0; i < N; i++) 
            cin >> v[i];
        cout << solve(v) << endl;
    }
    return 0;
}