536. Maximum Average Subarray II (Scaled)

Given an array and an integer k, find the contiguous subarray of length at least k that has the maximum average value. To keep the answer an exact integer, return floor(maxAverage * 100000). Use binary search on the average. The input is JSON {nums, k}.

Input: JSON {nums, k}.

Output: Integer — floor(maxAverage * 100000).

Examples

Input: {"nums":[1,12,-5,-6,50,3],"k":4}
Output: 1275000
Explanation: Max average 12.75 scaled by 100000.

Input: {"nums":[5],"k":1}
Output: 500000
Explanation: Average 5.0.

Input: {"nums":[1,2,3,4],"k":2}
Output: 350000
Explanation: Best average 3.5.

Constraints

• 1<=k<=n<=10^4
• -10^4<=value<=10^4

Asked by