在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 好听的元旦简短祝福语