C++で最大K個の配列要素の符号を反転することによる最大サブ配列の合計

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

コードの説明 −ここでは、配列を反転する最大k個の要素を見つける必要があります。これにより、この配列から作成されたサブ配列の合計が最大になります。

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

入力 −配列={1、-2、7、0} k =2

出力 − 10

説明 − -2である1つの要素のみを反転します。これにより、配列の合計が最大になる10になります。

この問題を解決するために、動的計画法を使用して、i ^th から配列の可能な最大の合計を見つけます。 j ^th へのインデックス インデックスを作成して配列maxSumij[i][j]に格納し、要素が反転した場合と要素が反転していない場合の両方のケースを考慮して、これが最良のケースを返します。これは、関数への再帰呼び出しを使用して行われます。最後に、maxSumij[i][j]行列から最大の要素を見つけます。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
#define right 2
#define left 4
int arraySumij[left][right];
int findSubarraySum(int i, int flips, int n, int a[], int k){
   if (flips > k)
      return -1e9;
   if (i == n)
      return 0;
   if (arraySumij[i][flips] != -1)
      return arraySumij[i][flips];
   int maxSum = 0;
   maxSum = max(0, a[i] + findSubarraySum(i + 1, flips, n, a, k));
   maxSum = max(maxSum, -a[i] + findSubarraySum(i + 1, flips + 1, n, a, k));
   arraySumij[i][flips] = maxSum;
   return maxSum;
}
int maxSubarraySumFlip(int a[], int n, int k){
   memset(arraySumij, -1, sizeof(arraySumij));
   int maxSum = -100;
   for (int i = 0; i < n; i++)
      maxSum = max(maxSum, findSubarraySum(i, 0, n, a, k));
   return maxSum;
}
int main() {
   int a[] = {-3, 56, -1, 8};
   int n = sizeof(a) / sizeof(a[0]);
   int k = 2;
   cout<<"Maximum subarry sum by fipping signs of at most "<<k<<" element is "<<maxSubarraySumFlip(a, n, k);
   return 0;
}

出力

Maximum subarry sum by fipping signs of at most 2 element is 66