সি++ প্রোগ্রাম: M নন-ওভারল্যাপিং সাবঅ্যারে (সাইজ K) এর সর্বোচ্চ যোগফল

সমস্যা বিবরণ

একটি অ্যারে এবং দুটি সংখ্যা M এবং K দেওয়া আছে। আমাদের কাজ হল অ্যারেতে M সংখ্যক সাইজ K-এর নন-ওভারল্যাপিং সাবঅ্যারের সর্বোচ্চ যোগফল খুঁজে বের করা। (অ্যারেতে এলিমেন্টের ক্রম অপরিবর্তিত থাকবে)। K হল সাবঅ্যারের সাইজ এবং M হল সাবঅ্যারের সংখ্যা। অনুমান করা হয় অ্যারের সাইজ m*k এর চেয়ে বড়। যদি টোটাল অ্যারে সাইজ K-এর গুণিতক না হয়, তবে শেষের আংশিক অ্যারেটি নেওয়া যাবে।

উদাহরণ

যদি অ্যারে = {2, 10, 7, 18, 5, 33, 0}, N = 7, M = 3 এবং K = 1 হয়, তবে আউটপুট হবে ৬১ কারণ সাবসেটটি হবে {33, 18, 10}

অ্যালগরিদম

একটি প্রি-সম (presum) অ্যারে তৈরি করুন, যাতে প্রতিটি ইনডেক্সে দেওয়া অ্যারেতে 'ইনডেক্স' থেকে 'ইনডেক্স + K' পর্যন্ত সব এলিমেন্টের যোগফল থাকে। এই সম অ্যারের সাইজ হবে n+1-k।
যদি আমরা সাইজ k-এর একটি সাবঅ্যারে ইনক্লুড করি, তবে সেই সাবঅ্যারের কোনো এলিমেন্টও আবার অন্য কোনো সাবঅ্যারেতে ব্যবহার করা যাবে না (ওভারল্যাপ হবেই)। তাই রিকারসিভ কল দিয়ে ইনক্লুড করা সাবঅ্যারের k সংখ্যক এলিমেন্ট বাদ দিন।
যদি একটি সাবঅ্যারে এক্সক্লুড করি, তবে সেই সাবঅ্যারের পরবর্তী k-1 엘িমেন্ট অন্য সাবঅ্যারেতে ব্যবহার করা যাবে। তাই রিকারসিভ কল দিয়ে শুধু সাবঅ্যারের প্রথম এলিমেন্টটি বাদ দিন।
শেষে max(ইনক্লুড করা যোগফল, এক্সক্লুড করা যোগফল) রিটার্ন করুন।

সি++ কোড উদাহরণ

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

void calculatePresumArray(int presum[], int arr[], int n, int k) {
    for (int i = 0; i < k; i++)
        presum[0] += arr[i];
    for (int i = 1; i <= n - k; i++)
        presum[i] = presum[i-1] + arr[i+k-1] - arr[i-1];
}

int maxSumMnonOverlappingSubarray(int presum[], int m, int size, int k, int start) {
    if (m == 0) return 0;
    if (start > size - 1) return 0;
    int includeMax = presum[start] + maxSumMnonOverlappingSubarray(presum, m - 1, size, k, start + k);
    int excludeMax = maxSumMnonOverlappingSubarray(presum, m, size, k, start + 1);
    return max(includeMax, excludeMax);
}

int main() {
    int arr[] = { 2, 10, 7, 18, 5, 33, 0 };
    int n = sizeof(arr)/sizeof(arr[0]);
    int m = 3, k = 1;
    int presum[n + 1 - k] = { 0 };
    calculatePresumArray(presum, arr, n, k);
    cout << "Maximum sum = " << maxSumMnonOverlappingSubarray(presum, m, n + 1 - k, k, 0) << endl;
    return 0;
}

আউটপুট

Maximum sum = 61