在C ++中最多转换两个元素后的最大子数组总和

在这个问题上，我们得到一个数组。我们的任务是创建一个程序，该程序在反转C ++中的最多两个元素之后将找到最大子数组和。

问题描述-在这里，我们必须找到在反转任意两个数字的符号时将产生最大和的子数组。

让我们举个例子来了解这个问题，

输入-数组= {-5、1、3、8，-2、4、7}

输出-30

解释-我们将考虑从索引0到6的元素，并将值-5和-2取反以得到最大和的数组。

为了解决这个问题，我们将使用动态编程方法。我们将检查大小为1到n（数组的长度）的所有子数组的最大和。因此，对于每个子数组，我们有三种情况-

情况1-反转子数组的两个元素后，子数组的最大和。

情况2-反转子数组的一个元素后，子数组的最大和。

情况3-反转子数组的零个元素后，子数组的最大和。

因此，对于我们进行的每次迭代，我们将找到数组maxsum的最大值以及当前元素，并将其初始化为最大值。

我们将最大和存储到名为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