ধরুন আমাদের একটি অ্যারে A আছে, আমাদের এটিকে বাম এবং ডানে দুটি সাবয়ারে ভাগ করতে হবে যাতে −
-
বাম সাবয়ারের প্রতিটি উপাদান ডান সাবয়ারের প্রতিটি উপাদানের থেকে কম বা সমান।
-
বাম এবং ডান সাব্যারে অ-খালি।
-
বাম সাবয়ারের সম্ভাব্য আকার সবচেয়ে ছোট।
এই ধরনের পার্টিশন করার পরে আমাদের বাম দৈর্ঘ্য খুঁজে বের করতে হবে। এটা নিশ্চিত যে এই ধরনের পার্টিশন বিদ্যমান।
সুতরাং ইনপুট যদি [5,0,3,8,6] এর মত হয়, তাহলে আউটপুট হবে 3, বাম অ্যারে যেমন হবে [5,0,3] এবং ডান সাবয়ারে হবে [8,6]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
n :=A এর আকার, n
আকারের একটি ম্যাক্সক্স অ্যারে তৈরি করুন -
minVal :=A
এর শেষ উপাদান -
maxx[0] :=A[0]
-
1 থেকে n – 1
রেঞ্জের জন্য i-
maxx[i] :=A[i] এবং A[i – 1]
এর সর্বোচ্চ
-
-
উত্তর :=A – 1 এর আকার
-
i রেঞ্জ n – 1 থেকে 1
এর মধ্যে-
minVal :=সর্বনিম্ন minVal এবং A[i]
-
যদি minVal>=max[i – 1] হয়, তাহলে উত্তর :=i
-
-
উত্তর ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int partitionDisjoint(vector <int>& A) {
int n = A.size();
vector <int> maxx(n);
int minVal = A[n - 1];
maxx[0] = A[0];
for(int i = 1; i < n; i++){
maxx[i] = max(A[i], maxx[i - 1]);
}
int ans = A.size() - 1;
for(int i = n - 1; i >= 1; i--){
minVal = min(minVal, A[i]);
if(minVal >= maxx[i - 1]){
ans = i;
}
}
return ans;
}
};
main(){
vector<int> v1 = {5,0,3,8,6};
Solution ob;
cout << (ob.partitionDisjoint(v1));
} ইনপুট
[5,0,3,8,6]
আউটপুট
3
