이 문제에서 크기가 n인 두 개의 배열 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 =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