Trong bài toán này, chúng ta được cung cấp hai mảng arr1 [] có kích thước n và arr2 [] có kích thước m. Nhiệm vụ của chúng ta là tạo một chương trình để tìm tổng mảng con tối đa không bao gồm các phần tử nhất định.
Mô tả sự cố - Chúng ta cần tìm tổng mảng con tối đa từ các phần tử của mảng arr1 [] không có trong arr2 [].
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr1[] = {4, 5, 7, 2, 9}, arr2[] = {1, 9, 2, 7} Đầu ra
9
Giải thích
arr1 after removal of elements of arr2[] = {4, 5}
Both can form a subarray, hence sum = 4+5 = 9. Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng Thuật toán Kadane trong đó wecan tìm thấy tất cả các chuỗi mảng lây nhiễm tích cực. Tìm tổng các alen của dãy con này và sau đó trả về giá trị tối đa của chúng. Nếu nó xuất hiện trong arr2, chúng tôi sẽ xóa cửa sổ hiện tại và đặt lại cửa sổ. Kiểm tra xem tổng có nhỏ hơnmaxSum không, maxSum =sum.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
The maximum Subarray Sum Excluding Certain Elements is 9
Giải pháp này có hiệu quả nhưng có thể có một cách tiếp cận tốt hơn để kiểm tra sự hiện diện của các phần tử trong mảng thứ hai, điều này sẽ tiết kiệm một số thời gian tính toán. Đây là một cách để làm điều đó bằng cách sử dụng bản đồ -
Trong cách tiếp cận này, chúng tôi sẽ sử dụng Thuật toán Kadane đã cập nhật của chúng tôi và một bản cập nhật khác sẽ được thực hiện bằng cách thay thế thuật toán tìm kiếm của chúng tôi bằng kiểm tra dựa trên bản đồ về sự hiện diện của phần tử trong mảng sẽ có hiệu lực.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
The maximum Subarray Sum Excluding Certain Elements is 9