C++-এ দুটি নন-ওভারল্যাপিং সাবঅ্যারের সর্বোচ্চ যোগফল (Maximum Sum Two Non-Overlapping Subarrays)

এই সমস্যাতে, ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে এবং একটি সংখ্যা k দেওয়া থাকে। আমাদের কাজ হল আকার k-এর দুটি নন-ওভারল্যাপিং (অন্যোন্যাশ্রয়ী/ডISTINCT) সাবঅ্যারে বের করা যাদের যোগফলের সমষ্টি সর্বোচ্চ।

উদাহরণ

ইনপুট: array = {7, 1, 6, 9, 2}, k = 2

আউটপুট: {7, 1}, {6, 9}

ব্যাখ্যা:

{7, 1}: sum = 8
{1, 6}: sum = 7
{6, 9}: sum = 15
{9, 2}: sum = 11
সর্বোচ্চ দুটি নন-ওভারল্যাপিং: {7,1} এবং {6,9}

প্রিফিক্স সম (Prefix Sum) পদ্ধতি

প্রিফিক্স সম অ্যারে তৈরি করে O(1)-এ যেকোনো সাবঅ্যারের যোগফল বের করা যায়। তারপর পেছন থেকে আগে দিকে ট্রাভার্স করে দুটি সাবঅ্যারের সর্বোচ্চ যোগফল খুঁজে বের করুন।

C++ প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

int findSubArraySum(int sum[], int i, int j) {
    if (i == 0) return sum[j];
    else return (sum[j] - sum[i - 1]);
}

void maxSubarray(int arr[], int N, int K) {
    int prefixsum[N];
    prefixsum[0] = arr[0];
    for (int i = 1; i < N; i++)
        prefixsum[i] = prefixsum[i - 1] + arr[i];
    
    pair<int, int> resIndex = make_pair(N - 2 * K, N - K);
    int maxSubarraySum = findSubArraySum(prefixsum, N - 2 * K, N - K - 1) 
                        + findSubArraySum(prefixsum, N - K, N - 1);
    
    pair<int, int> secondSubarrayMax = make_pair(N - K, findSubArraySum(prefixsum, N - K, N - 1));
    
    for (int i = N - 2 * K - 1; i >= 0; i--) {
        int cur = findSubArraySum(prefixsum, i + K, i + 2 * K - 1);
        if (cur >= secondSubarrayMax.second)
            secondSubarrayMax = make_pair(i + K, cur);
        
        cur = findSubArraySum(prefixsum, i, i + K - 1) + secondSubarrayMax.second;
        if (cur >= maxSubarraySum) {
            maxSubarraySum = cur;
            resIndex = make_pair(i, secondSubarrayMax.first);
        }
    }
    
    cout << "{ ";
    for (int i = resIndex.first; i < resIndex.first + K; i++)
        cout << arr[i] << " ";
    cout << "}" << endl << "{ ";
    for (int i = resIndex.second; i < resIndex.second + K; i++)
        cout << arr[i] << " ";
    cout << "}" << endl;
}

int main() {
    int arr[] = {2, 5, 1, 2, 7, 3, 0};
    int N = sizeof(arr) / sizeof(int);
    int K = 2;
    cout << "Two non-overlapping subarrays with maximum sum are:\n";
    maxSubarray(arr, N, K);
    return 0;
}

আউটপুট

Two non-overlapping subarrays with maximum sum are
{ 2 5 } { 7 3 }