দুই নন-ওভারল্যাপিং সাবঅ্রে সর্বোচ্চ সমষ্টি C++-এ

একটি ইন্টিজার অ্যারে A এবং দুটি দৈর্ঘ্য L ও M দেওয়া আছে। দুটি নন-ওভারল্যাপিং সাবঅ্রে (একটার দৈর্ঘ্য L, অন্যটার M) খুঁজে বের করতে হবে যাতে তাদের সমষ্টি সর্বোচ্চ হয়। সাবঅ্রে দুটি যেকোনো ক্রমে থাকতে পারে (L তারপর M, অথবা M তারপর L)।

উদাহরণ

ইনপুট: A = [0,6,5,2,3,5,1,9,4], L = 1, M = 2

আউটপুট: 20

ব্যাখ্যা: L=1 এর জন্য সাবঅ্রে [9] (সমষ্টি ৯), M=2 এর জন্য [6,5] (সমষ্টি ১১) → মোট ২০।

অ্যালগরিদম (প্রিফিক্স/সাফিক্স ম্যাক্স)

1. चारটি অ্যারে বানান: leftL, leftM, rightL, rightM।
2. leftL[i] = ইন্ডেক্স i পর্যন্ত দৈর্ঘ্য L-এর সাবঅ্রের সর্বোচ্চ সমষ্টি।
3. rightL[i] = ইন্ডেক্স i থেকে শেষ পর্যন্ত দৈর্ঘ্য L-এর সাবঅ্রের সর্বোচ্চ সমষ্টি।
4. M-এর জন্যও একইভাবে হিসাব করুন।
5. সব সম্ভাব্য বিভাজন পয়েন্টে চেক করুন:
   • L বামে, M ডানে: leftL[i] + rightM[i+1]
   • M বামে, L ডানে: leftM[i] + rightL[i+1]
6. সর্বোচ্চ মান রিটার্ন করুন।

C++ কোড উদাহরণ

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

class Solution {
public:
    int maxSumTwoNoOverlap(vector& A, int L, int M) {
        int n = A.size();
        vector leftL(n), leftM(n), rightL(n), rightM(n);
        
        // Left max for L
        int sum = 0;
        for (int i = 0; i < L; i++) sum += A[i];
        leftL[L-1] = sum;
        for (int i = L, j = 0; i < n; i++, j++) {
            sum += A[i] - A[j];
            leftL[i] = max(leftL[i-1], sum);
        }
        
        // Left max for M
        sum = 0;
        for (int i = 0; i < M; i++) sum += A[i];
        leftM[M-1] = sum;
        for (int i = M, j = 0; i < n; i++, j++) {
            sum += A[i] - A[j];
            leftM[i] = max(leftM[i-1], sum);
        }
        
        // Right max for L
        sum = 0;
        for (int i = n-1; i > n-1-L; i--) sum += A[i];
        rightL[n-L] = sum;
        for (int i = n-L-1, j = n-1; i >= 0; i--, j--) {
            sum += A[i] - A[j];
            rightL[i] = max(rightL[i+1], sum);
        }
        
        // Right max for M
        sum = 0;
        for (int i = n-1; i > n-1-M; i--) sum += A[i];
        rightM[n-M] = sum;
        for (int i = n-M-1, j = n-1; i >= 0; i--, j--) {
            sum += A[i] - A[j];
            rightM[i] = max(rightM[i+1], sum);
        }
        
        int ans = 0;
        for (int i = L-1; i <= n-1-M; i++)
            ans = max(ans, leftL[i] + rightM[i+1]);
        for (int i = M-1; i <= n-1-L; i++)
            ans = max(ans, leftM[i] + rightL[i+1]);
        
        return ans;
    }
};

int main() {
    Solution ob;
    vector v = {0,6,5,2,3,5,1,9,4};
    cout << ob.maxSumTwoNoOverlap(v, 1, 2);
    return 0;
}

ইনপুট

[0,6,5,2,3,5,1,9,4] 1 2

আউটপুট

20