এই সমস্যায়, আমাদের ধনাত্মক এবং ঋণাত্মক মান এবং একটি পূর্ণসংখ্যা k সমন্বিত n আকারের একটি অ্যারে [] দেওয়া হয়েছে। আমাদের কাজ হল k দৈর্ঘ্যের সর্বাধিক গড় সাব্যারে খুঁজে বের করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: arr[] ={4, -1, 5, 6, -2, 4} k =3
আউটপুট: 10
ব্যাখ্যা:
সর্বাধিক যোগফল সহ সাইজ 3 এর সাবয়ারের হল -1, 5, 6 =10
সমাধান পদ্ধতি
একটি অক্সিলিয়ারি অ্যারে ব্যবহার করে সমস্যার সমাধান করা হয় অ্যারেতে বর্তমান সূচক পর্যন্ত ক্রমবর্ধমান সমষ্টি সংরক্ষণ করতে।
সাব্যারেগুলির যোগফল খুঁজে পেতে, আমাদের সাব্যারের অবস্থানের সূচকগুলির মধ্যে পার্থক্য গণনা করতে হবে৷
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
int findMaxSubArrayAverage(int arr[], int n, int k) {
if (k > n)
return -1;
int *auxSumArray = new int[n];
auxSumArray[0] = arr[0];
for (int i=1; i<n; i++)
auxSumArray[i] = auxSumArray[i-1] + arr[i];
int maxSum = auxSumArray[k-1], subEndIndex = k-1;
for (int i=k; i<n; i++) {
int sumVal = auxSumArray[i] - auxSumArray[i-k];
if (sumVal > maxSum) {
maxSum = sumVal;
subEndIndex = i;
}
}
return subEndIndex - k + 1;
}
int main() {
int arr[] = {4, -1, 5, 6, -2, 4};
int k = 3;
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum average subarray of length "<<k<<" begins at index "<<findMaxSubArrayAverage(arr, n, k);
return 0;
} আউটপুট
The maximum average subarray of length 3 begins at index 1
