C ++中最多删除一个元素的最大和子数组
在这个问题上，我们得到一个数组。我们的任务是创建一个程序，该程序将找到最大的总和子数组，该数组最多可以删除c ++中的一个元素。
基本上，我们需要找到一个元素，将其删除后可为数组中剩余的元素提供最大的总和。
让我们举个例子来了解这个问题，
输入-数组= {5、1、9、2，-1、7}
输出-24
解释-我们从数组中删除了-1，并且总和成为所有可能结果的最大值。
解决此问题的一种方法是找到数组的最小元素，然后找到数组所有剩余元素的总和。
但是在这里，不应用元素去除条件，kadane的算法将更好地解决该问题。因此，在这里我们将以这样的方式计算最大和：我们也将从头到尾找到直到第i个元素的和。
然后使用开始和结束求和数组检查在跳过哪个ith元素，然后在跳过给定元素后打印总和。
示例
显示我们解决方案实施情况的程序，
#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
以上是 C ++中最多删除一个元素的最大和子数组 的全部内容， 来源链接： utcz.com/z/358407.html
