C++で要素を1つまで削除して得られる最大部分配列和を求める方法

整数の配列が与えられたとき、最大で1つの要素を削除できる非空（空でない）の連続部分配列における最大の合計値を求める問題を考えてみましょう。言い換えると、ある部分配列を選び、必要に応じてその中から1つの要素だけを取り除き、残った要素の合計が最大になるようにするというものです。ただし、削除を行った後でも部分配列には少なくとも1つの要素が残っている必要がある点に注意してください。

たとえば、入力が [1,-2,0,3] の場合、出力は 4 になります。-2 を削除すれば、残りの要素の合計 1+0+3=4 が最大となるためです。

解法のアプローチ

この問題は動的計画法（DP）を用いることで、線形時間 O(n) で効率的に解くことができます。基本的な考え方はカダネのアルゴリズム（Kadane's Algorithm）の拡張です。

ここでは、次の2つの状態を持つ変数を管理します。

• suffix_with_deletion：現在の位置で終わる部分配列のうち、「すでに1つの要素を削除済み」の場合の最大合計
• suffix_without_deletion：現在の位置で終わる部分配列のうち、「まだ何も削除していない」場合の最大合計

具体的な手順は以下の通りです。

• n := 配列のサイズ、ans := a[0] と初期化する
• suffix_with_deletion := 0、suffix_without_deletion := a[0] とする
• i = 1 から n-1 まで繰り返す
  • suffix_with_deletion := max(suffix_with_deletion + a[i], suffix_without_deletion)
  • suffix_without_deletion := max(a[i], suffix_without_deletion + a[i])
  • ans := max(ans, suffix_without_deletion, suffix_with_deletion)
• 最後に ans を返す

ポイントは、「a[i] を新たに削除する」ケースを suffix_with_deletion への遷移で表現している点です。つまり、これまで削除なしで積み上げてきた合計（suffix_without_deletion）から、現在の要素 a[i] を捨てることで、削除済み状態へ移行できます。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int maximumSum(vector<int>& a) {
        int n = a.size();
        int ans = a[0];
        int suffix_with_deletion = 0;
        int suffix_without_deletion = a[0];
        for(int i = 1; i < n; i++){
            suffix_with_deletion = max(suffix_with_deletion + a[i], suffix_without_deletion);
            suffix_without_deletion = max(a[i], suffix_without_deletion + a[i]);
            ans = max({ans, suffix_without_deletion, suffix_with_deletion});
        }
        return ans;
    }
};
main(){
    vector<int> v = {1,-2,0,3};
    Solution ob;
    cout << ob.maximumSum(v);
}

入力

[1,-2,0,3]

出力

4

まとめ

このアルゴリズムでは、配列を一度走査するだけで答えが求まるため、時間計算量は O(n)、使用する補助変数は定数個のみなので空間計算量は O(1) となります。「1要素の削除を許す最大部分配列和」のような問題は、状態を「削除あり／なし」に分けてDPを設計することで、カダネのアルゴリズムを自然に拡張できる好例といえるでしょう。