চলুন প্রোগ্রামটি সম্পূর্ণ করার ধাপগুলো দেখি।
- অ্যারে শুরু করুন।
- অ্যারের সমস্ত শূন্যকে -1 করুন।
- পূর্ববর্তী সূচীগুলি সংরক্ষণ করার জন্য একটি মানচিত্র একটি খালি মানচিত্র রাখুন৷
- শুরুতে যোগফল 0, সর্বোচ্চ দৈর্ঘ্য 0 এবং শেষ সূচক -1।
- একটি লুপ লিখুন যা n.
- পর্যন্ত পুনরাবৃত্তি করে
- সমষ্টিতে বর্তমান উপাদান যোগ করুন।
- যদি যোগফল 0 এর সমান হয়।
- i + 1 দিয়ে সর্বাধিক দৈর্ঘ্য আপডেট করুন।
- এবং আই-এ শেষ সূচক।
- যদি যোগফলটি পূর্ববর্তী সমষ্টির মানচিত্রে উপস্থিত থাকে এবং i - পূর্ববর্তী সূচীপত্র[সমষ্টি] সর্বোচ্চ দৈর্ঘ্যের চেয়ে বেশি হয়।
- সর্বোচ্চ দৈর্ঘ্য এবং শেষ সূচক আপডেট করুন।
- অন্যথায় আগের ইনডেক্স ম্যাপে যোগফল যোগ করুন।
- প্রিন্ট করুন প্রারম্ভিক সূচী শেষের সূচক - maxLength + 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
উপসংহার
টিউটোরিয়ালে আপনার কোন প্রশ্ন থাকলে মন্তব্য বিভাগে উল্লেখ করুন।
