通过翻转C ++中最多K个数组元素的符号来获得最大子数组总和

在这个问题中，我们得到一个数组和一个整数k。我们的任务是创建一个程序，该程序通过翻转C ++中最多k个数组元素的符号来找到最大子数组和。

代码说明-在这里，我们将不得不找到最多k个元素来翻转数组，这将使从该数组创建的子数组的总和最大。

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

输入-数组= {1，-2，7，0} k = 2

输出-10

说明-我们将仅翻转一个元素-2，这使数组和10为最大可能。

为了解决这个问题，我们将使用动态编程方法，该方法将找到从^第i^个索引到^第j^个索引的数组的最大可能和，并将其存储在数组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