ในปัญหานี้ เราได้รับอาร์เรย์สองอาร์เรย์ 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. แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือการใช้ Algorithm ของ Kadane ซึ่งเราสามารถค้นหาลำดับการแพร่ระบาดที่เป็นบวกของอาร์เรย์ได้ทั้งหมด ค้นหาผลรวมของอัลลิเมนต์ของลำดับย่อยนี้แล้วคืนค่าสูงสุด เราจะอัปเดตอัลกอริธึมโดยพิจารณาจากข้อเท็จจริงที่ว่าเราไม่จำเป็นต้องพิจารณาองค์ประกอบ 2[] สำหรับอาร์เรย์ย่อยสูงสุด และสำหรับสิ่งนี้ เราจะค้นหาองค์ประกอบโดยใช้อัลกอริธึมการค้นหา หากมีอยู่ใน 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
โซลูชันนี้มีประสิทธิภาพ แต่อาจมีวิธีที่ดีกว่าในการตรวจสอบการมีอยู่ขององค์ประกอบในอาร์เรย์ที่สอง ซึ่งจะช่วยประหยัดเวลาในการคำนวณ นี่คือวิธีการทำโดยใช้แผนที่ -
ในแนวทางนี้ เราจะใช้อัลกอริธึมของ 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
