ধরুন আমাদের পূর্ণসংখ্যার একটি অ্যারে আছে; আমাদের দুটি নন-ওভারল্যাপিং সাব্যারেতে উপাদানের সর্বোচ্চ যোগফল খুঁজে বের করতে হবে। এই সাবয়ারের দৈর্ঘ্য হল L এবং M.
তাই আরও সুনির্দিষ্টভাবে আমরা বলতে পারি যে, আমাদের সবচেয়ে বড় V খুঁজে বের করতে হবে যার জন্য
V =(A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+ M-1]) এবং হয় −
-
0 <=i
-
0 <=j
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=A
এর আকার -
n আকারের একটি অ্যারের leftL সংজ্ঞায়িত করুন, n আকারের একটি অ্যারে leftM সংজ্ঞায়িত করুন
-
n আকারের একটি অ্যারের rightL সংজ্ঞায়িত করুন, n আকারের একটি অ্যারের rightM সংজ্ঞায়িত করুন
-
ret :=0, temp :=0
-
শুরু করার জন্য i :=0, যখন i
-
temp =temp + A[i]
-
-
শুরু করার জন্য i :=L, j :=0, যখন i
-
leftL[i − 1] :=তাপমাত্রার সর্বোচ্চ এবং x যেখানে x 0 যখন i − 2 <0 অন্যথায় x =leftL[i − 2]
-
temp =temp + A[i]
-
temp =temp − A[j]
-
-
leftL[n − 1] :=তাপমাত্রার সর্বোচ্চ, এবং x যেখানে x 0 যখন n − 2 <0 অন্যথায় x :=leftL[n − 2]
-
তাপমাত্রা :=0
-
শুরু করার জন্য i :=0, যখন i
-
temp =temp + A[i]
-
-
শুরু করার জন্য i :=M, j :=0, যখন i
-
temp =temp + A[i]
-
temp =temp - A[j]
-
-
leftM[n − 1] :=তাপমাত্রার সর্বোচ্চ এবং x যখন x :=0 যদি n - 2 <0 অন্যথায় x :=leftM[n − 2]
-
তাপমাত্রা :=0
-
শুরু করার জন্য i :=n − 1, যখন i> n − 1 − L, i কমিয়ে 1 do −
-
temp =temp + A[i]
-
-
শুরু করার জন্য i :=n − 1 − L, j :=n − 1, যখন i>=0, i 1 কমাতে, j 1 দ্বারা হ্রাস করুন, −
করুন-
rightL[i + 1] :=তাপমাত্রার সর্বোচ্চ এবং x যেখানে x 0 হলে i + 2>=n অন্যথায় x =rightL[i + 2]
-
temp =temp + A[i]
-
temp =temp − A[j]
-
-
rightL[0] :=সর্বোচ্চ তাপমাত্রা এবং rightL[1]
-
তাপমাত্রা :=0
-
শুরু করার জন্য i :=n − 1, যখন i> n − 1 − M, i 1 do −
কমিয়ে দিন-
temp =temp + A[i]
-
-
শুরু করার জন্য i :=n − 1 − M, j :=n − 1, যখন i>=0, i 1 কমাতে, j কমাতে 1, −
করুন-
rightM[i + 1] :=temp এবং x এর সর্বোচ্চ, যেখানে x 0 যখন i + 2>=n অন্যথায় x :=rightM[i + 2]
-
temp =temp + A[i]
-
temp =temp − A[j]
-
-
rightM[0] :=সর্বোচ্চ তাপমাত্রা এবং rightM[1]
-
শুরু করার জন্য i :=L − 1, যখন i <=n − 1 − M, i 1 do −
বাড়ান-
ret :=ret এবং leftL[i] + rightM[i + 1]
-এর সর্বোচ্চ
-
-
শুরু করার জন্য i :=M − 1, যখন i <=n − 1 − L, i 1 do −
বাড়ান-
ret :=ret এবং leftM[i] + rightL[i + 1]
-এর সর্বোচ্চ
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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);
vector <int> leftM(n);
vector <int> rightL(n);
vector <int> rightM(n);
int ret = 0;
int temp = 0;
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]);
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]);
//out(leftM);
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]);
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]);
for(int i = L − 1; i <= n − 1 − M; i++){
ret = max(ret, leftL[i] + rightM[i + 1]);
}
for(int i = M − 1; i <= n − 1 − L; i++){
ret = max(ret, leftM[i] + rightL[i + 1]);
}
return ret;
}
};
main(){
Solution ob;
vector<int> v1 = {0,6,5,2,3,5,1,9,4};
cout << (ob.maxSumTwoNoOverlap(v1, 1, 2));
} ইনপুট
[0,6,5,2,3,5,1,9,4] 1 2
আউটপুট
20
