C ++程序中排除某些元素的最大子数组总和

在这个问题中，我们得到了两个大小为n的数组arr1 []和大小为m的arr2 []。我们的任务是创建一个程序来查找不包括某些元素的最大子数组和。

问题描述-我们需要从数组arr1 []中不存在于arr2 []中的元素中找到最大子数组和。

让我们举个例子来了解这个问题，

输入项

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算法，在该算法中，我们可以找到数组的所有正传染性序列。找到该子序列所有元素的总和，然后返回它们的最大值。我们将基于不需要为max子数组考虑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<<"排除某些元素的最大子数组总和为
   "<<calcMaxSubArraySum(arr1, arr2, n, m);
   return 0;
}

输出结果

排除某些元素的最大子数组总和为 9

该解决方案是有效的，但是可以有更好的方法来检查第二个数组中元素的存在，这将节省一些计算时间。这是使用映射的一种方法-

在这种方法中，我们将使用更新的Kadane算法，并且通过将搜索算法替换为基于映射的检查算法来检查数组中元素的存在，从而完成另一项更新，这将是有效的。

示例

该程序说明了我们解决方案的工作原理，

#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<<"排除某些元素的最大子数组总和为 "<<calcMaxSubArraySum(arr1, arr2, n, m);
   return 0;
}

输出结果

排除某些元素的最大子数组总和为 9