在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 婚前女儿生日祝福语简短