বারবার সংযোজনের পর তৈরি অ্যারেতে সর্বোচ্চ সাবঅ্যারে যোগফল (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের n আকারের একটি অ্যারে arr[] এবং একটি পূর্ণসংখ্যা k দেওয়া আছে। আমাদের কাজ হল বারবার সংযোজনের পর তৈরি অ্যারেতে সর্বোচ্চ সাবঅ্যারে যোগফল খুঁজে বের করার প্রোগ্রাম তৈরি করা।

আমরা arr কে k বার রিপিট করে যে অ্যারেটি তৈরি হবে, সেটি থেকে সাবঅ্যারে নিয়ে সর্বোচ্চ যোগফল বের করব।

arr[] = {-9, -5, 14, 6} k = 2

26

বারবার রিপিট করার পর নতুন অ্যারে: {-9, -5, 14, 6, -9, -5, 14, 6}
সর্বোচ্চ যোগফল वाले সাবঅ্যারে = {14, 6, -9, -5, 14, 6}
যোগফল = 26

একটি সহজ সমাধান হল সংযোজন দ্বারা তৈরি নতুন অ্যারে তৈরি করা এবং তারপর সর্বোচ্চ যোগফল वाले সাবঅ্যারে খুঁজে বের করা। এর জন্য সেরা পদ্ধতি হবে ক্যাডেনস অ্যালগরিদম (Kadane's Algorithm) ব্যবহার করা।

#include 
using namespace std;

int calcMaxSubArraySum(int arr[], int n, int k) {
    int newArr[2 * n];
    for (int i = 0; i < k * n; i++)
        newArr[i] = arr[i % n];
    
    int maxSum = -1000, sum = 0;
    for (int i = 0; i < k * n; i++) {
        sum = sum + newArr[i];
        if (maxSum < sum)
            maxSum = sum;
        if (sum < 0)
            sum = 0;
    }
    return maxSum;
}

int main() {
    int arr[] = { -9, -5, 14, 6 };
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum subarray sum in an array created after repeated concatenation is " << calcMaxSubArraySum(arr, n, k);
    return 0;
}

The maximum subarray sum in an array created after repeated concatenation is 26

এই পদ্ধতি ভালো হলেও একটি আরও দক্ষ পদ্ধতি আছে মডুলার অ্যারিথমেটিক ব্যবহার করে।

মডুলার অ্যারিথমেটিক (Modular Arithmetic) হল যখন আমরা মডুলো অপারেটর ব্যবহার করে সমীকরণের অবশিষ্টাংশ বের করি।

সমস্যা সমাধানের জন্য, আমরা বারবার সংযোজন করে অ্যারে না বানিয়ে মডুলার অ্যারিথমেটিক ব্যবহার করব। বাকি সমাধান একই থাকবে।

#include 
using namespace std;

int calcMaxSubArraySum(int arr[], int n, int k) {
    int maxSum = -1000, sum = 0;
    for (int i = 0; i < k * n; i++) {
        sum = sum + arr[i % n];
        if (maxSum < sum)
            maxSum = sum;
        if (sum < 0)
            sum = 0;
    }
    return maxSum;
}

int main() {
    int arr[] = { -9, -5, 14, 6 };
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The maximum subarray sum in an array created after repeated concatenation is " << calcMaxSubArraySum(arr, n, k);
    return 0;
}

The maximum subarray sum in an array created after repeated concatenation is 26