Given an array with positive and negative numbers, find the maximum average subarray which length should be greater or equal to given length k.
Note
It’s guaranteed that the size of the array is greater or equal to k.
Example
No.1
Input:
[1,12,-5,-6,50,3]
3
Output:
15.667
Explanation:
(-6 + 50 + 3) / 3 = 15.667
No.2
Input:
[5]
1
Output:
5.000
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
public double (int[] nums, int k) {
double left = Double.MAX_VALUE;
double right = Double.MIN_VALUE;
for (int num : nums) {
left = Math.min(left, num);
right = Math.max(right, num);
}
while (right - left > 1e-5) {
double mid = left + (right - left) / 2;
if (isMidLarger(nums, k, mid))
right = mid;
else
left = mid;
}
return left;
}
private boolean isMidLarger(int[] nums, int k, double mid) {
double sum = 0;
double preSum = 0;
double minSum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i] - mid;
if (i >= k) {
preSum += nums[i - k] - mid;
minSum = Math.min(minSum, preSum);
}
if (i >= k - 1 && sum - minSum >= 0)
return false;
}
return true;
}
|
近期评论