在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 教师闺蜜祝福语简短