ผลรวมเซิร์ฟอาร์เรย์สูงสุดโดยไม่รวมองค์ประกอบบางอย่างในโปรแกรม C++

ในปัญหานี้ เราได้รับสองอาร์เรย์ arr1[] ขนาด n และ arr2[] ขนาด m ภารกิจของเราคือสร้างโปรแกรมเพื่อหาผลรวมเซิร์ฟอาร์เรย์สูงสุดโดยไม่รวมองค์ประกอบบางอย่าง

คำอธิบายปัญหา

เราต้องหาผลรวมเซิร์ฟอาร์เรย์สูงสุดจากองค์ประกอบของอาร์เรย์ arr1[] ที่ไม่อยู่ใน arr2[]

ตัวอย่าง

อินพุต

arr1[] = {4, 5, 7, 2, 9}, arr2[] = {1, 9, 2, 7}

เอาต์พุต

9

คำอธิบาย

arr1 หลังจากนำองค์ประกอบของ arr2[] ออก = {4, 5} 
ทั้งสองสามารถสร้างเซิร์ฟอาร์เรย์ได้ ดังนั้นผลรวม = 4+5 = 9

แนวทางแก้ปัญหา

วิธีแก้ที่ง่ายคือการใช้อัลกอริทึมของ Kadane ซึ่งเราสามารถหาลำดับติดกันบวกทั้งหมดของอาร์เรย์ได้ หาผลรวมขององค์ประกอบทั้งหมดของลำดับย่อยนี้แล้วคืนค่าสูงสุดของพวกเขา เราจะอัปเดตอัลกอริทึมตามข้อเท็จจริงที่ว่าเราไม่ต้องพิจารณาองค์ประกอบของ arr2[] สำหรับ max subarray และสำหรับสิ่งนี้เราจะค้นหาองค์ประกอบโดยใช้อัลกอริทึมการค้นหา หากมีอยู่ใน arr2 เราจะล้างหน้าต่างปัจจุบันและรีเซ็ตหน้าต่าง ตรวจสอบว่าผลรวมน้อยกว่า maxSum maxSum = sum

ตัวอย่างโค้ด (วิธีการค้นหาแบบ Binary Search)

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#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

วิธีแก้นี้มีประสิทธิภาพแต่สามารถมีแนวทางที่ดีกว่าสำหรับการตรวจสอบความมีอยู่ขององค์ประกอบในอาร์เรย์ที่สองซึ่งจะประหยัดเวลาการคำนวณบ้าง นี่คือวิธีทำโดยใช้ map

ในแนวทางนี้ เราจะใช้อัลกอริทึม Kadane ที่อัปเดตแล้ว และการอัปเดตอีกอย่างหนึ่งจะทำโดยการแทนที่อัลกอริทึมการค้นหาของเราด้วยการตรวจสอบการมีอยู่ขององค์ประกอบในอาร์เรย์แบบใช้ map ซึ่งจะมีประสิทธิภาพ

ตัวอย่างโค้ด (วิธีใช้ unordered_map)

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#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

The maximum Subarray Sum Excluding Certain Elements is 9