C++で最大1要素を削除した後の部分配列の最大和を最大化する方法

問題文

N個の整数からなる配列 arr[] が与えられます。まず最大部分配列和を求め、その部分配列から最大で1つの要素を削除したとき、合計が最大になるようにします。つまり、削除できる要素は最大で1つまでとし、削除後の合計を最大化することがこの問題の目的です。

例として、入力配列が {1, 2, 3, -2, 3} の場合を考えてみましょう。この配列の最大部分配列は配列全体 {1, 2, 3, -2, 3} で、その和は7です。ここで -2 を削除すると、残りの配列は次のようになります。

{1, 2, 3, 3} となり、和は9でこれが最大となります。

アルゴリズム

この問題は、カダネのアルゴリズム（Kadane's algorithm）を応用することで効率的に解くことができます。

1. まず、カダネのアルゴリズムを使って最大部分配列和 sum を求めます。
2. 次に、いくつかの変更を加えたカダネのアルゴリズムを再度適用します。今度は現在の部分配列内の最小要素も同時に追跡し、currentMax が sum に達した時点で、その部分配列の最小要素を記録します（部分配列の長さが1の場合は削除しないものとして0を記録）。
3. 最終的な答えは、sum から記録した最小値を引いた値になります。

実装例

#include <bits/stdc++.h>
using namespace std;
int getMaxSubarraySum(int *arr, int n){
   int max = INT_MIN;
   int currentMax = 0;
   for (int i = 0; i < n; ++i) {
      currentMax = currentMax + arr[i];
      if (max < currentMax) {
         max = currentMax;
      }
      if (currentMax < 0) {
         currentMax = 0;
      }
   }
   return max;
}
int getMaxSum(int *arr, int n){
   int cnt = 0;
   int minVal = INT_MAX;
   int minSubarr = INT_MAX;
   int sum = getMaxSubarraySum(arr, n);
   int max = INT_MIN;
   int currentMax = 0;
   for (int i = 0; i < n; ++i) {
      currentMax = currentMax + arr[i];
      ++cnt;
      minSubarr = min(arr[i], minSubarr);
      if (sum == currentMax) {
         if (cnt == 1) {
            minVal = min(minVal, 0);
         } else {
            minVal = min(minVal, minSubarr);
         }
      }
      if (currentMax < 0) {
         currentMax = 0;
         cnt = 0;
         minSubarr = INT_MAX;
      }
   }
   return sum - minVal;
}
int main(){
   int arr[] = {1, 2, 3, -2, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Maximum sum = 9