数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中删除最多一个元素的最大子数组和
在这个问题中，我们得到一个数组。我们的任务是创建一个程序，该程序将在 C++ 中找到删除最多一个元素的最大子数组和。
基本上，我们需要找到一个元素，当删除该元素时，数组中剩余元素的总和最大。
让我们举一个例子来理解这个问题，
输入 − 数组 = {5, 1, 9, 2, -1, 7}
输出 − 24
说明 − 我们从数组中删除了 -1，并且总和成为所有可能结果中的最大值。
解决此问题的一种方法是找到数组的最小元素，然后找到数组中所有剩余元素的总和。
但是在这里，没有应用元素删除条件，Kadane 算法将以更好的方式解决问题。因此，在这里我们将计算最大和，这样我们将从开始到第 i 个元素以及从结束到第 i 个元素计算和。
然后检查使用开始和结束和数组跳过哪个第 i 个元素，然后打印跳过给定元素后的和。
示例
程序演示了我们解决方案的实现，
#include <bits/stdc++.h>
using namespace std;
int maxSubarraySum(int array[], int n){
int startSum[n], endSum[n];
int maxSum = array[0], overAllMax = array[0];
startSum[0] = array[0];
for (int i = 1; i < n; i++){
maxSum = max(array[i], maxSum + array[i]);
overAllMax = max(overAllMax, maxSum);
startSum[i] = maxSum;
}
maxSum = endSum[n-1] = array[n-1];
for (int i = n-2; i >= 0; i--){
maxSum = max(array[i], maxSum + array[i]);
overAllMax = max(overAllMax, maxSum);
endSum[i] = maxSum;
}
int SubArraySum = overAllMax;
for (int i = 1; i < n - 1; i++)
SubArraySum = max(SubArraySum, startSum[i - 1] + endSum[i + 1]);
return SubArraySum;
}
int main()
{
int array[] = {5, 7, 1, -1, 4, 2, 9};
int n = sizeof(array) / sizeof(array[0]);
cout<;"The maximum subarray after removing one element is "<<maxSubarraySum(array, n);
return 0;
}输出
The maximum subarray after removing one element is 28
更新于: 2020-06-03
126 次浏览
广告