C++で最大1つの要素を削除する最大合計サブ配列

この問題では、配列が与えられます。私たちのタスクは、c++で最大1つの要素を削除する最大合計サブ配列を見つけるプログラムを作成することです。

基本的に、削除されたときに配列に残っている要素の最大合計を提供する1つの要素を見つける必要があります。

問題を理解するために例を見てみましょう

入力 −配列={5、1、9、2、-1、7}

出力 − 24

説明 −配列から-1を削除し、合計がすべての可能な結果の最大値になりました。

この問題の解決策の1つは、配列の最小要素を見つけてから、配列の残りのすべての要素の合計を見つけることです。

ただし、ここでは、要素の削除条件は適用されません。kadaneのアルゴリズム より良い方法で問題を解決します。したがって、ここでは、最初と最後から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