ধরুন, একটি সংখ্যার লিস্ট nums এবং একটি মান k দেওয়া আছে। আমাদের এমন একটি সাবলিস্ট (Subarray) খুঁজে বের করতে হবে যার দৈর্ঘ্য কমপক্ষে k এবং গড় মান সর্বোচ্চ।
উদাহরণস্বরূপ, nums = [2, 10, -50, 4, 6, 6], k = 3 হলে আউটপুট হবে 5.33333333, কারণ সাবলিস্ট [4, 6, 6]-এর গড় সর্বোচ্চ।
সমাধানের ধাপসমূহ (বাইনারি সার্চ + প্রিফিক্স সাম)
left :=
min(nums), right :=max(nums)প্রথম
kউপাদানের যোগফলs, প্রাথমিক গড়largest_avg = s / k।যখন
left <= right:mid = (left + right) // 2স্লাইডিং উইন্ডো দিয়ে চেক করুন যে
midগড় অর্জন করা সম্ভব কিনা।sum1, sum2, cntম্যানেজ করুন এবং সর্বোচ্চ গড়avgট্র্যাক করুন।largest_avg = max(largest_avg, avg)যদি
avg > midহয়, তবেleft = mid + 1, অন্যথায়right = mid - 1।
largest_avgরিটার্ন করুন।
পাইথন কোড উদাহরণ
class Solution:
def solve(self, nums, k):
left, right = min(nums), max(nums)
s = sum(nums[:k])
largest_avg = s / k
while left <= right:
mid = (left + right) // 2
sum1 = s
avg = s / k
sum2 = 0
cnt = 0
for i in range(k, len(nums)):
sum1 += nums[i]
sum2 += nums[i - k]
cnt += 1
avg = max(avg, sum1 / (cnt + k))
if sum2 / cnt <= mid:
sum1 -= sum2
cnt = 0
sum2 = 0
avg = max(avg, sum1 / (cnt + k))
largest_avg = max(largest_avg, avg)
if avg > mid:
left = mid + 1
else:
right = mid - 1
return largest_avg
ob = Solution()
nums = [2, 10, -50, 4, 6, 6]
k = 3
print(ob.solve(nums, k))ইনপুট
[2, 10, -50, 4, 6, 6], k = 3
আউটপুট
5.333333333333333
