Maximum Average Segment
InterviewTime limit1sMemory limit64 MB
Find the largest average over all contiguous subarrays of length at least K and print it truncated to six decimals.
- Level
Medium6 of 10
- Topics
- Binary search, Prefix sum
- Solved
- No attempts yet
Problem
You are given an array of integers. Among all contiguous subarrays whose length is at least , find the one with the largest average and report that average.
The average of a subarray is the sum of its elements divided by the number of elements.
Input
The first line contains two integers and separated by a space (, ).
The second line contains the array elements separated by spaces ().
Output
Let be the largest possible average. Print on one line, truncated to six digits after the decimal point. That is, print split into an integer part and six decimal digits. Digits past the sixth are cut off, never rounded.
is a rational number whose denominator is at most , so integer arithmetic computes it exactly. Print all six decimal digits even when they are zeros.