आइए प्रोग्राम को पूरा करने के चरण देखते हैं।
- सरणी आरंभ करें।
- सरणी में सभी शून्य को -1 बनाएं।
- पिछले इंडेक्स स्टोर करने के लिए एक खाली मैप रखें।
- योग को 0, अधिकतम लंबाई को 0 और अंतिम इंडेक्स को -1 पर आरंभ करें।
- एक लूप लिखें जो n तक पुनरावृति करता है।
- वर्तमान तत्व को योग में जोड़ें।
- यदि योग 0 के बराबर है।
- अधिकतम लंबाई को i + 1 से अपडेट करें।
- और अंतिम इंडेक्स को i पर।
- यदि योग पिछले योग मैप में मौजूद है और i - previousIndexes[sum] अधिकतम लंबाई से बड़ा है।
- अधिकतम लंबाई और अंतिम इंडेक्स अपडेट करें।
- अन्यथा योग को पिछले इंडेक्स मैप में जोड़ें।
- शुरुआती इंडेक्स endingIndex - maxLength + 1 और अंतिम इंडेक्स endingIndex प्रिंट करें।
उदाहरण
आइए कोड देखते हैं।
#include <bits/stdc++.h>
using namespace std;
void findTheSubArray(int arr[], int n) {
unordered_map<int, int> previousIndexes;
int sum = 0, maxLength = 0, endingIndex = -1;
for (int i = 0; i < n; i++) {
arr[i] = arr[i] == 0 ? -1 : 1;
}
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == 0) {
maxLength = i + 1;
endingIndex = i;
}
if (previousIndexes.find(sum) != previousIndexes.end()) {
if (maxLength < i - previousIndexes[sum]) {
maxLength = i - previousIndexes[sum];
endingIndex = i;
}
}else {
previousIndexes[sum] = i;
}
}
cout << endingIndex - maxLength + 1 << " " << endingIndex << endl;
}
int main() {
int arr[] = { 1, 1, 0, 0, 0, 1, 1, 1, 0 };
findTheSubArray(arr, 9);
return 0;
}
आउटपुट
यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्नलिखित परिणाम मिलेगा।
1 8
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उन्हें टिप्पणी अनुभाग में उल्लेख करें।
