C++で解く：重複しない2つの部分配列の最大合計を求める効率的なアルゴリズム

整数型の配列 A が与えられたとき、互いに重なり合わない2つの部分配列（サブアレイ）に含まれる要素の合計の最大値を求めることを考えます。ここで、2つの部分配列の長さはそれぞれ L と M です。

問題の定義

より正確には、次の式を満たす最大の V を求めます。

V = (A[i] + A[i+1] + … + A[i+L−1]) + (A[j] + A[j+1] + … + A[j+M−1])

このとき、インデックスは以下のいずれかの条件を満たす必要があります。

• 0 ≤ i ＜ i + L − 1 ＜ j ＜ j + M − 1 ＜ 配列Aのサイズ（長さLの部分配列が左、長さMの部分配列が右）

• 0 ≤ j ＜ j + M − 1 ＜ i ＜ i + L − 1 ＜ 配列Aのサイズ（長さMの部分配列が左、長さLの部分配列が右）

解法のアプローチ

この問題は、「各位置までの前方からの最大値」と「各位置以降の後方からの最大値」を事前に計算しておくことで、O(n) の時間計算量で効率的に解けます。具体的には、次の4つの補助配列を用意します。

• leftL[i]：インデックス i まで（i を含む）の範囲で、長さ L の部分配列の合計の最大値

• leftM[i]：同じ範囲で、長さ M の部分配列の合計の最大値

• rightL[i]：インデックス i 以降の範囲で、長さ L の部分配列の合計の最大値

• rightM[i]：同じ範囲で、長さ M の部分配列の合計の最大値

これらを用いて「Lが左・Mが右」と「Mが左・Lが右」の2パターンをすべて試し、その最大値が答えとなります。

アルゴリズムの手順

1. n := 配列 A のサイズとする

2. サイズ n の配列 leftL、leftM、rightL、rightM を定義する

3. ret := 0、temp := 0 で初期化する

4. 先頭から長さ L のウィンドウの合計を temp に求め、ウィンドウを1つずつ右へスライドしながら、leftL[i] に「位置 i までの長さ L の部分配列の合計の最大値」を記録していく

5. 同じ手順で leftM を構築する

6. 今度は末尾から逆方向に同様の処理を行い、rightL と rightM を構築する

7. i を L − 1 から n − 1 − M まで動かし、ret = max(ret, leftL[i] + rightM[i + 1]) で更新する（Lが左・Mが右のパターン）

8. i を M − 1 から n − 1 − L まで動かし、ret = max(ret, leftM[i] + rightL[i + 1]) で更新する（Mが左・Lが右のパターン）

9. ret を返す

それでは、理解を深めるために実際の実装を見てみましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
      int n = A.size();
      vector <int> leftL(n);
      vector <int> leftM(n);
      vector <int> rightL(n);
      vector <int> rightM(n);
      int ret = 0;
      int temp = 0;
      // 前方から長さLの最大合計を記録
      for(int i = 0; i < L; i++){
         temp += A[i];
      }
      for(int i = L, j = 0; i < n; i++, j++){
         leftL[i − 1] = max(temp, i − 2 < 0 ? 0 : leftL[i − 2]);
         temp += A[i];
         temp −= A[j];
      }
      leftL[n − 1] = max(temp, n − 2 < 0 ? 0 : leftL[n − 2]);
      // 前方から長さMの最大合計を記録
      temp = 0;
      for(int i = 0; i < M; i++){
         temp += A[i];
      }
      for(int i = M, j = 0; i < n; i++, j++){
         leftM[i − 1] = max(temp, i − 2 < 0 ? 0 : leftM[i − 2]);
         temp += A[i];
         temp −= A[j];
      }
      leftM[n − 1] = max(temp, n − 2 < 0 ? 0 : leftM[n − 2]);
      // 後方から長さLの最大合計を記録
      temp = 0;
      for(int i = n − 1; i > n − 1 − L; i−−){
         temp += A[i];
      }
      for(int i = n − 1 − L, j = n − 1; i >= 0 ; i−−, j−− ){
         rightL[i + 1] = max(temp, (i + 2 >= n ? 0 : rightL[i + 2]));
         temp += A[i];
         temp −= A[j];
      }
      rightL[0] = max(temp, rightL[1]);
      // 後方から長さMの最大合計を記録
      temp = 0;
      for(int i = n − 1; i > n − 1 − M; i−−){
         temp += A[i];
      }
      for(int i = n − 1 − M, j = n − 1; i >= 0 ; i−−, j−− ){
         rightM[i + 1] = max(temp, (i + 2 >= n ? 0 : rightM[i + 2]));
         temp += A[i];
         temp −= A[j];
      }
      rightM[0] = max(temp, rightM[1]);
      // Lが左・Mが右のパターン
      for(int i = L − 1; i <= n − 1 − M; i++){
         ret = max(ret, leftL[i] + rightM[i + 1]);
      }
      // Mが左・Lが右のパターン
      for(int i = M − 1; i <= n − 1 − L; i++){
         ret = max(ret, leftM[i] + rightL[i + 1]);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v1 = {0,6,5,2,3,5,1,9,4};
   cout << (ob.maxSumTwoNoOverlap(v1, 1, 2));
}

入力

[0,6,5,2,3,5,1,9,4]
1
2

出力

20

出力の解説

この例では、長さ1の部分配列として [9]（合計9）、長さ2の部分配列として [5,6]（合計11）を選ぶことで、両者は重ならず、合計は 9 + 11 = 20 となり、これが最大値です。

まとめ

本手法では、スライディングウィンドウで部分配列の合計を更新しながら前計算を行うため、全体の時間計算量は O(n)、空間計算量も O(n) に抑えられます。全ての分割位置の組み合わせを総当たりする O(n²) の素朴な解法と比べて、大きな入力に対しても高速に動作するのが特徴です。