在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
热门推荐
10 圣诞祝福语简短小学
11 祖国七十华诞简短祝福语
12 老师送的祝福语简短
13 生日祝福语大全女生简短
14 祝女性生日祝福语简短
15 牛年女神节祝福语简短
16 情人表白祝福语简短大气
17 老公开业祝福语简短
18 官宣新年祝福语简短