通过翻转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
以上是 通过翻转C ++中最多K个数组元素的符号来获得最大子数组总和 的全部内容， 来源链接： utcz.com/z/334883.html
