C++での2つの重複しないサブアレイの最大合計

これを解決するには、次の手順に従います-

• n：=Aのサイズ

• サイズnの配列leftLを定義し、サイズnの配列leftMを定義します

• サイズnの配列rightLを定義し、サイズnの配列rightMを定義します

• ret：=0、temp：=0

• iを初期化する場合：=0、i

  • temp =temp + A [i]

• i：=L、j：=0を初期化する場合、i

  • leftL [i − 1]：=温度とxの最大値。ここで、i − 2 <0の場合はxは0、それ以外の場合はx =leftL [i − 2]

  • temp =temp + A [i]

  • temp =temp − A [j]

• leftL [n − 1]：=温度の最大値、およびx（n − 2 <0の場合はxは0、それ以外の場合はx：=leftL [n − 2]

• temp：=0

• iを初期化する場合：=0、i

  • temp =temp + A [i]

• i：=M、j：=0を初期化する場合、i

  • temp =temp + A [i]

  • temp =temp-A [j]

• leftM [n − 1]：=温度の最大値とxの場合はx：=0（n-2 <0の場合）それ以外の場合はx：=leftM [n − 2]

• temp：=0

• i：=n − 1を初期化する場合、i> n − 1 − Lの場合、iを1つ減らしますdo −

  • temp =temp + A [i]

• iを初期化する場合：=n − 1 − L、j：=n − 1、i> =0の場合、iを1減らし、jを1減らし、do −

  • rightL [i + 1]：=温度とxの最大値。ここで、i + 2> =nの場合はxは0、それ以外の場合はx =rightL [i + 2]

  • temp =temp + A [i]

  • temp =temp − A [j]

• rightL [0]：=tempとrightL[1]

  の最大値

• temp：=0

• i：=n − 1を初期化する場合、i> n − 1 − Mの場合、iを1つ減らしますdo −

  • temp =temp + A [i]

• iを初期化する場合：=n − 1 − M、j：=n − 1、i> =0の場合、iを1減らし、jを1減らし、do −

  • rightM [i + 1]：=温度とxの最大値。ここで、i + 2> =nの場合はxは0、それ以外の場合はx：=rightM [i + 2]

  • temp =temp + A [i]

  • temp =temp − A [j]

• rightM [0]：=tempとrightM[1]

  の最大値

• iを初期化する場合：=L − 1、i <=n − 1 − Mの場合、iを1つ増やしますdo −

  • ret：=retとleftL[i] + rightM [i + 1]

    の最大値

• iを初期化する場合：=M − 1、i <=n − 1 − Lの場合、iを1つ増やしますdo −

  • ret：=retとleftM[i] + rightL [i + 1]

    の最大値

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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;
      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]);
      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]);
      //out(leftM);
      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]);
      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]);
      for(int i = L − 1; i <= n − 1 − M; i++){
         ret = max(ret, leftL[i] + rightM[i + 1]);
      }
      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