आइए कार्यक्रम को पूरा करने के चरणों को देखें।
- सरणी प्रारंभ करें।
- सरणी के सभी शून्यों को -1 बना दें।
- पिछली अनुक्रमणिकाओं को संग्रहीत करने के लिए एक नक्शा खाली नक्शा रखें।
- सम को 0 से प्रारंभ करें, अधिकतम लंबाई 0 से और अंत अनुक्रमणिका -1 से प्रारंभ करें।
- एक लूप लिखें जो n तक पुनरावृत्त हो।
- योग में वर्तमान तत्व जोड़ें।
- यदि योग 0 के बराबर है।
- अधिकतम लंबाई को i + 1 से अपडेट करें।
- और अनुक्रमणिका को i पर समाप्त करना।
- यदि योग पिछले योग मानचित्र में मौजूद है और i - पिछले इंडेक्स [योग] अधिकतम लंबाई से अधिक है।
- अधिकतम लंबाई और समाप्ति अनुक्रमणिका अपडेट करें।
- अन्यथा पिछले इंडेक्स मैप में योग जोड़ें।
- शुरुआती इंडेक्स एंडिंगइंडेक्स - मैक्सलेंथ + 1 और एंडिंग इंडेक्स एंडिंगइंडेक्स प्रिंट करें।
उदाहरण
आइए कोड देखें।
#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
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उनका टिप्पणी अनुभाग में उल्लेख करें।