C++で最大2つの要素を反転した後の最大サブアレイ合計

この問題では、配列が与えられます。私たちのタスクは、C++で最大2つの要素を反転した後に最大のサブ配列の合計を見つけるプログラムを作成することです。

問題の説明 −ここでは、配列の任意の2つの数値の符号を反転したときに最大の合計を生成するサブ配列を見つける必要があります。

問題を理解するために例を見てみましょう

入力 −配列={-5、1、3、8、-2、4、7}

出力 − 30

説明 −インデックス0から6までの要素を検討し、値-5と-2を反転して、最大合計の配列を取得します。

この問題を解決するために、動的計画法を使用します。サイズ1からn（配列の長さ）のすべてのサブ配列の最大合計をチェックします。したがって、サブアレイごとに3つのケースがあります-

ケース1 −サブアレイの2つの要素を反転した後のサブアレイの最大合計。

ケース2 −サブアレイの1つの要素を反転した後のサブアレイの最大合計。

ケース3 −サブアレイのゼロ要素を反転した後のサブアレイの最大合計。

したがって、反復ごとに、配列の最大値と現在の要素を見つけて、その最大値を初期化します。

最大合計をmaxSumという名前の2D配列に格納します。そして、最終的なmaxSumは、2D配列のすべての要素の最大値です。

例

ソリューションの実装を示すプログラム

#include <bits/stdc++.h>
using namespace std;
int findMaxSubarraySum(int a[], int n) {
   int maxSubarraySum = 0;
   int* arr = new int[n + 1];
   for (int i = 1; i <= n; i++)
      arr[i] = a[i - 1];
   int** maxSum = new int*[n + 1];
   for (int i = 0; i <= n; i++)
      maxSum[i] = new int[3];
   for (int i = 1; i <= n; ++i) {
      maxSum[i][0] = max(arr[i], maxSum[i - 1][0] + arr[i]);
      maxSum[i][1] = max(0, maxSum[i - 1][0]) - arr[i];
      if (i >= 2)
      maxSum[i][1] = max(maxSum[i][1], maxSum[i - 1][1] + arr[i]);
      if (i >= 2)
         maxSum[i][2] = maxSum[i - 1][1] - arr[i];
      if (i >= 3)
         maxSum[i][2] = max(maxSum[i][2], maxSum[i - 1][2] + arr[i]);
      maxSubarraySum = max(maxSubarraySum, maxSum[i][0]);
      maxSubarraySum = max(maxSubarraySum, maxSum[i][1]);
      maxSubarraySum = max(maxSubarraySum, maxSum[i][2]);
   }
   return maxSubarraySum;
}
int main(){
   int arr[] = {-5, 1, 3, 8, -2, 4, 7};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum subarray sum after inverting at most two elements is "<<findMaxSubarraySum(arr, n);
   return 0;
}

出力

Maximum subarray sum after inverting at most two elements is 30