নির্দিষ্ট উপাদান বাদ দিয়ে সর্বোচ্চ সাবঅ্যারে যোগফল (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের n আকারের arr1[] এবং m আকারের arr2[] - দুটি অ্যারে দেওয়া আছে। আমাদের কাজ হল নির্দিষ্ট উপাদান বাদ দিয়ে সর্বোচ্চ সাবঅ্যারে যোগফল খুঁজে বের করার প্রোগ্রাম তৈরি করা।

আমাদের arr1[]-এর উপাদান থেকে সর্বোচ্চ সাবঅ্যারে যোগফল বের করতে হবে যেগুলো arr2[]-এ নেই।

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

9

arr2[]-এর উপাদান বাদ দিয়ে arr1 = {4, 5}
দুটোই সাবঅ্যারে তৈরি করতে পারে, তাই যোগফল = 4+5 = 9।

একটি সহজ সমাধান হল ক্যাডেনস অ্যালগরিদম (Kadane's Algorithm) ব্যবহার করা যেখানে আমরা অ্যারেতে সব পজিটিভ সংলগ্ন সিকোয়েন্স বের করি। এই সাবসিকোয়েন্সের সব উপাদানের যোগফল বের করে সর্বোচ্চটি ফেরত দিতে হবে। আমরা অ্যালগরিদম আপডেট করব এই ফ্যাক্টের ভিত্তিতে যে arr2[]-এর উপাদানগুলো সর্বোচ্চ সাবঅ্যারের জন্য বিবেচনা করতে হবে না। এবং এর জন্য আমরা সার্চিং অ্যালগরিদম ব্যবহার করে উপাদান খুঁজে বের করব। যদি arr2-এ উপাদানটি থাকে, তবে আমরা করেন্ট উইন্ডো ক্লিয়ার করব এবং উইন্ডো রিসেট করব। চেক করব যোগফল যদি maxSum-এর চেয়ে কম হয়, তবে maxSum = sum।

#include 
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

এই সমাধান কার্যকর হলেও উপাদান চেক করার জন্য আরও ভালো পদ্ধতি আছে ম্যাপ ব্যবহার করে যা কম্পিউটেশন টাইম বাঁচাবে।

#include 
using namespace std;

int calcMaxSubArraySum(int arr1[], int arr2[], int n, int m) {
    unordered_map 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