数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中最多反转两个元素后的最大子数组和
在这个问题中，我们给定一个数组。我们的任务是创建一个程序，该程序将找到在 C++ 中最多反转两个元素后的最大子数组和。
问题描述 - 在这里，我们必须找到反转数组中任意两个数字的符号后产生最大和的子数组。
让我们举个例子来理解这个问题，
输入 - 数组 = {-5, 1, 3, 8, -2, 4, 7}
输出 - 30
解释 - 我们将考虑从索引 0 到 6 的元素，并将值 -5 和 -2 反转以获得具有最大和的数组。
为了解决这个问题，我们将使用动态规划方法。我们将检查大小为 1 到 n（数组长度）的所有子数组的最大和。因此，对于每个子数组，我们有三种情况 -
情况 1 - 反转子数组的两个元素后的子数组的最大和。
情况 2 - 反转子数组的一个元素后的子数组的最大和。
情况 3 - 反转子数组的零个元素后的子数组的最大和。
因此，对于我们拥有的每次迭代，我们将找到数组的最大和以及当前元素的最大值，并将其初始化为最大值。
我们将最大和存储到一个名为 maxSum 的二维数组中。最终的 maxSum 是二维数组中所有元素的最大值。
示例
显示我们解决方案实现的程序，
#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
更新于: 2020年6月3日
195 次查看
广告