資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式中排除某些元素的最大子陣列和
在這個問題中，我們得到了兩個陣列 arr1[]，大小為 n，和 arr2[]，大小為 m。我們的任務是建立一個程式來查詢排除某些元素的最大子陣列和。
問題描述 − 我們需要從陣列 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 演算法，在該演算法中，我們可以找到陣列的所有正連續序列。找到此子序列中所有元素的總和，然後返回其中的最大值。我們將根據以下事實更新演算法：我們不需要考慮 arr2[] 元素的最大子陣列，為此，我們將使用搜索演算法搜尋元素。如果它存在於 arr2 中，我們將清除當前視窗並重置視窗。檢查總和是否小於 maxSum，maxSum = sum。
示例
程式說明我們解決方案的工作原理，
#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
此解決方案有效，但可能存在更好的方法來檢查第二個陣列中是否存在元素，這將節省一些計算時間。以下是如何使用對映來實現的方法 -
在這種方法中，我們將使用我們更新後的 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<<"The maximum Subarray Sum Excluding Certain Elements is "<<calcMaxSubArraySum(arr1, arr2, n, m);
return 0;
}輸出
The maximum Subarray Sum Excluding Certain Elements is 9
更新於: 2020-12-09
117 次瀏覽
廣告