C++-এ পুনরাবৃত্তি সংযোজন後 সর্বোচ্চ সাবঅ্যারে যোগফল (Maximum subarray sum in an array created after repeated concatenation)

এই টিউটোরিয়ালে আমরা একটি অ্যারে K বার পুনরাবৃত্তি করে তৈরি করা অ্যারেতে সর্বোচ্চ সাবঅ্যারে যোগফল বের করার আলোচনা করব।

একটি অ্যারে এবং পূর্ণসংখ্যা K দেওয়া থাকবে। দেওয়া অ্যারেটি K বার পুনরাবৃত্তি করলে সৃষ্ট অ্যারেতে সর্বোচ্চ উপাদানযুক্ত সাবঅ্যারে বের করতে হবে।

উদাহরণ

#include<bits/stdc++.h>
using namespace std;
//returning sum of maximum subarray
int maxSubArraySumRepeated(int a[], int n, int k) {
    int max_so_far = INT_MIN, max_ending_here = 0;
    for (int i = 0; i < n*k; i++) {
        max_ending_here = max_ending_here + a[i%n];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
        if (max_ending_here < 0) max_ending_here = 0;
    }
    return max_so_far;
}
int main() {
    int a[] = {10, 20, -30, -1};
    int n = sizeof(a)/sizeof(a[0]);
    int k = 3;
    cout << "Maximum contiguous sum is " << maxSubArraySumRepeated(a, n, k);
    return 0;
}

আউটপুট

Maximum contiguous sum is 30