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