मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है, हमें सरणी को कुछ विभाजनों में विभाजित करना होगा, और प्रत्येक विभाजन को व्यक्तिगत रूप से क्रमबद्ध करना होगा। अब उन्हें संयोजित करने के बाद हमें एक क्रमबद्ध सरणी मिलेगी। हमें अधिकतम संख्या में विभाजन ज्ञात करने होंगे जो हम कर सकते थे?
इसलिए, यदि इनपुट [3,2,4,5,5] जैसा है, तो आउटपुट 4 होगा, क्योंकि हम [3,2], [4], [5], [5] जैसे विभाजन कर सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
सीएनटी:=1
-
n :=गिरफ्तारी का आकार
-
एक सरणी को परिभाषित करें maxOfLeft आकार n
-
n आकार के minOfRight की एक सरणी परिभाषित करें
-
maxOfLeft[0] :=arr[0]
-
इनिशियलाइज़ करने के लिए मैं :=1, जब i
-
maxOfLeft[i] :=अधिकतम maxOfLeft[i - 1] और arr[i]
-
-
minOfRight[n - 1] =arr[n - 1]
-
इनिशियलाइज़ करने के लिए i :=n - 2, जब i>=0, अपडेट करें (i से 1 घटाएं), −
करें-
minOfRight[i] :=न्यूनतम minOfRight[i + 1] और arr[i]
-
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
अगर minOfRight[i + 1]>=maxOfLeft[i], तो −
-
(cnt 1 से बढ़ाएँ)
-
-
-
वापसी सीएनटी
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxChunksToSorted(vector<int>& arr) {
int cnt = 1;
int n = arr.size();
vector<int> maxOfLeft(n);
vector<int> minOfRight(n);
maxOfLeft[0] = arr[0];
for (int i = 1; i < n; i++)
maxOfLeft[i] = max(maxOfLeft[i - 1], arr[i]);
minOfRight[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
minOfRight[i] = min(minOfRight[i + 1], arr[i]);
for (int i = 0; i < n - 1; i++) {
if (minOfRight[i + 1] >= maxOfLeft[i])
cnt++;
}
return cnt;
}
};
main(){
Solution ob;
vector<int> v = {3,2,4,5,5};
cout << (ob.maxChunksToSorted(v));
} इनपुट
{3,2,4,5,5} आउटपुट
4