একটি পূর্ণসংখ্যা অ্যারে দেওয়া থাকলে, যোগফল শূন্য হওয়া সবচেয়ে বড় সাবঅ্যারের দৈর্ঘ্য বের করতে হবে। না পাওয়া গেলে ০ রিটার্ন করুন।
ইনপুট-১
N = 8, A[] = {15, -5, -1, 5, 1, 4}
আউটপুট
4
ব্যাখ্যা
সবচেয়ে বড় শূন্য-যোগফল সাবঅ্যারে: {-5, -1, 5, 1} দৈর্ঘ্য ৪।
ইনপুট-২
N = 5, A[] = {3, 2, 4, 8, -1}
আউটপুট
0
সমাধানের পদ্ধতি
হ্যাশ টেবিল (prefix sum) ব্যবহার করে O(n) সময়ে সমাধান করা যায়।
unordered_map<int,int>দিয়ে prefix sum -> ইন্ডেক্স সংরক্ষণ করুন।- প্রতিটি এলিমেন্টে রানিং সাম `sum` বজায় রাখুন।
- যদি `sum == 0` হয়, ম্যাক্স লেন্থ আপডেট করুন।
- যদি `sum` ম্যাপে আগে থেকে থাকে, তবে সাবঅ্যারের দৈর্ঘ্য = `i - mp[sum]`।
- নতুন sum হলে ম্যাপে ইনসার্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int lenMax(int *arr, int size) {
unordered_map<int,int> mp;
int sum = 0, maxlen = 0;
for (int i = 0; i < size; i++) {
sum += arr[i];
if (arr[i] == 0 && maxlen == 0) maxlen = 1;
if (sum == 0) maxlen = i + 1;
if (mp.find(sum) != mp.end())
maxlen = max(maxlen, i - mp[sum]);
else
mp[sum] = i;
}
return maxlen;
}
int main() {
int N = 8, A[N] = {15,-2,2,-8,1,7,10,23};
cout << lenMax(A, N) << endl;
return 0;
}
আউটপুট
5
সবচেয়ে বড় শূন্য-যোগফল সাবঅ্যারে: {-2, 2, -8, 1, 7} দৈর্ঘ্য ৫।
