C++ में दो नॉन-ओवरलैपिंग सबएरे का अधिकतम योग

मान लीजिए हमारे पास पूर्णांकों की एक सरणी A है; हमें दो नॉन-ओवरलैपिंग (गैर-अतिव्यापी) सबएरे के तत्वों का अधिकतम योग ज्ञात करना है। इन सबएरे की लंबाई L और M है।

अधिक सटीक रूप से, हमें सबसे बड़ा V ढूंढना है जिसके लिए:

V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1])

और या तो:

• 0 <= i < i+L-1 < j < j+M-1 < A.size(), या
• 0 <= j < j+M-1 < i < i+L-1 < A.size()

समाधान दृष्टिकोण (प्रीफिक्स सम और स्लाइडिंग विंडो)

हम चार सरणियों की गणना करते हैं:

• leftL[i] - इंडेक्स i तक बाएं से L-लंबाई सबएरे का अधिकतम योग
• leftM[i] - इंडेक्स i तक बाएं से M-लंबाई सबएरे का अधिकतम योग
• rightL[i] - इंडेक्स i से दाएं L-लंबाई सबएरे का अधिकतम योग
• rightM[i] - इंडेक्स i से दाएं M-लंबाई सबएरे का अधिकतम योग

फिर हम दो स्थितियों की जांच करते हैं: L-सबएरे बाएं और M-सबएरे दाएं, या इसके विपरीत।

उदाहरण (C++ कोड)

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

class Solution { 
public: 
    int maxSumTwoNoOverlap(vector<int>& A, int L, int M) { 
        int n = A.size(); 
        vector<int> leftL(n), leftM(n), rightL(n), rightM(n); 
        int ret = 0, temp = 0; 
        
        // leftL 
        for (int i = 0; i < L; i++) temp += A[i]; 
        for (int i = L, j = 0; i < n; i++, j++) { 
            leftL[i-1] = max(temp, i-2 < 0 ? 0 : leftL[i-2]); 
            temp += A[i]; 
            temp -= A[j]; 
        } 
        leftL[n-1] = max(temp, n-2 < 0 ? 0 : leftL[n-2]); 
        
        // leftM 
        temp = 0; 
        for (int i = 0; i < M; i++) temp += A[i]; 
        for (int i = M, j = 0; i < n; i++, j++) { 
            leftM[i-1] = max(temp, i-2 < 0 ? 0 : leftM[i-2]); 
            temp += A[i]; 
            temp -= A[j]; 
        } 
        leftM[n-1] = max(temp, n-2 < 0 ? 0 : leftM[n-2]); 
        
        // rightL 
        temp = 0; 
        for (int i = n-1; i > n-1-L; i--) temp += A[i]; 
        for (int i = n-1-L, j = n-1; i >= 0; i--, j--) { 
            rightL[i+1] = max(temp, i+2 >= n ? 0 : rightL[i+2]); 
            temp += A[i]; 
            temp -= A[j]; 
        } 
        rightL[0] = max(temp, rightL[1]); 
        
        // rightM 
        temp = 0; 
        for (int i = n-1; i > n-1-M; i--) temp += A[i]; 
        for (int i = n-1-M, j = n-1; i >= 0; i--, j--) { 
            rightM[i+1] = max(temp, i+2 >= n ? 0 : rightM[i+2]); 
            temp += A[i]; 
            temp -= A[j]; 
        } 
        rightM[0] = max(temp, rightM[1]); 
        
        // L बाएं, M दाएं 
        for (int i = L-1; i <= n-1-M; i++) 
            ret = max(ret, leftL[i] + rightM[i+1]); 
        // M बाएं, L दाएं 
        for (int i = M-1; i <= n-1-L; i++) 
            ret = max(ret, leftM[i] + rightL[i+1]); 
        
        return ret; 
    } 
}; 

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

इनपुट

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

आउटपुट

20