C++プログラムの特定の要素を除く最大サブアレイ合計

この問題では、サイズnの2つの配列arr1[]とサイズmのarr2[]が与えられます。私たちのタスクは、特定の要素を除いた最大のサブ配列の合計を見つけるプログラムを作成することです。

問題の説明 −arr2[]に存在しない配列arr1[]の要素から最大のサブ配列の合計を見つける必要があります。

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

入力

arr1[] = {4, 5, 7, 2, 9}, arr2[] = {1, 9, 2, 7}

出力

9

説明

arr1 after removal of elements of arr2[] = {4, 5}
Both can form a subarray, hence sum = 4+5 = 9.

ソリューションアプローチ

この問題の簡単な解決策は、Kadaneのアルゴリズムを使用することです。このアルゴリズムでは、配列のすべての正の伝染性シーケンスを見つけることができます。このサブシーケンスのすべての要素の合計を見つけて、それらの最大値を返します。最大サブ配列のarr2 []要素を考慮する必要がないという事実に基づいてアルゴリズムを更新します。このため、検索アルゴリズムを使用して要素を検索します。 arr2に存在する場合は、現在のウィンドウをクリアしてウィンドウをリセットします。合計がmaxSum未満かどうかを確認します。maxSum=合計。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;
int isInArr2(int arr2[], int start, int end, int searchEle){
   if (end >= start) {
      int mid = start + (end − start) / 2;
      if (arr2[mid] == searchEle)
      return true;
      if (arr2[mid] > searchEle)
      return isInArr2(arr2, start, mid − 1, searchEle);
      return isInArr2(arr2, mid + 1, end, searchEle);
   }
   return false;
}
int calcMaxSubArraySum(int arr1[], int arr2[], int n, int m){
   int maxSum = −1, sum = 0;
   for (int i = 0; i < n; i++) {
      if (isInArr2(arr2, 0, m, arr1[i])) {
         sum = 0;
         continue;
      }
      sum = max(arr1[i], sum + arr1[i]);
      maxSum = max(maxSum, sum);
   }
   return maxSum;
}
int main(){
   int arr1[] = { 5, 4, 7, 2, 9 };
   int arr2[] = { 1, 9, 2, 7 };
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int m = sizeof(arr2) / sizeof(arr2[0]);
   cout<<"The maximum Subarray Sum Excluding Certain Elements is
   "<<calcMaxSubArraySum(arr1, arr2, n, m);
   return 0;
}

出力

The maximum Subarray Sum Excluding Certain Elements is 9

このソリューションは効果的ですが、2番目の配列に要素が存在するかどうかを確認するためのより良いアプローチがあり、計算時間を節約できます。これが地図を使ってそれをする方法です-

このアプローチでは、更新されたKadaneのアルゴリズムを使用し、検索アルゴリズムをマップベースのチェックに置き換えて、配列内の要素の存在を確認することで、もう1つの更新を行います。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
int calcMaxSubArraySum(int arr1[], int arr2[], int n, int m){
   unordered_map<int,int> checkVal;
   for(int i=0;i<m;i++)
   checkVal[arr2[i]] = 1;
   int maxSum = −1, sum = 0;
   for (int i = 0; i < n; i++) {
      if (checkVal[arr1[i]]==1) {
         sum = 0;
         continue;
      }
      sum = max(arr1[i], sum + arr1[i]);
      maxSum = max(maxSum, sum);
   }
   return maxSum;
}
int main(){
   int arr1[] = { 5, 4, 7, 2, 9 };
   int arr2[] = { 1, 9, 2, 7 };
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int m = sizeof(arr2) / sizeof(arr2[0]);
   cout<<"The maximum Subarray Sum Excluding Certain Elements is "<<calcMaxSubArraySum(arr1, arr2, n, m);
   return 0;
}

出力

The maximum Subarray Sum Excluding Certain Elements is 9