Given an array consisting of n integers, find the contiguous subarray whose length is greater than or equal to k that has the maximum average value. And you need to output the maximum average value.
Example 1:
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation:
when length is 5, maximum average value is 10.8,
when length is 6, maximum average value is 9.16667.
Thus return 12.75.
Note:
- 1 <=
k<=n<= 10,000. - Elements of the given array will be in range [-10,000, 10,000].
- The answer with the calculation error less than 10-5 will be accepted.
Idea 1. Brute force, use the idea on maximum subarray(Leetcode 53), for any pairs (i, j), j - i >= k-1, 0 <= i <= j < nums.length, check whether the sum of nums[i..j] is greater than the maximum sum so far.
Time complexity: O(n2)
Space complexity: O(1)
public class Solution {
public double findMaxAverage(int[] nums, int k) {
double maxAverage = Integer.MIN_VALUE;
for(int i = 0; i < nums.length; ++i) {
double sum = 0;
for(int j = i; j < nums.length; ++j) {
sum += nums[j];
if(j-i + 1 >= k) {
maxAverage = Math.max(maxAverage, sum/(j-i+1));
}
}
}
return maxAverage;
}
}
Idea 1.a Brute force, use the idea on Maximum Average Subarray I (Leetcode 643). Linearly find all the maximum average subarray for subarray length >= k.
public class Solution {
public double findMaxAverageWithLengthK(int[] nums, int k) {
double sum = 0;
for(int i = 0; i < k; ++i) {
sum += nums[i];
}
double maxSum = sum;
for(int i = k; i < nums.length; ++i) {
sum = sum + nums[i] - nums[i-k];
maxSum = Math.max(maxSum, sum);
}
return maxSum/k;
}
public double findMaxAverage(int[] nums, int k) {
double maxAverage = Integer.MIN_VALUE;
for(int i = k; i < nums.length; ++i) {
double average = findMaxAverageWithLengthK(nums, i);
maxAverage = Math.max(maxAverage, average);
}
return maxAverage;
}
}
Idea 2. Smart idea, use two techniques
1. Use binary search to guess the maxAverage, minValue in the array <= maxAverage <= maxValue in the array, assumed the guesed maxAverage is mid, if there exists a subarray with length >= k whos average is bigger than mid, then the maxAverage must be located between [mid, maxValue], otherwise between [minValue, mid].
2. How to efficiently check if there exists a subarray with length >= k whos average is bigger than mid? do you still remember the cumulative sum in maximum subArray? maximum sum subarray with length >= k can be computed by cumu[j] - min(cumu[i]) where j - i + 1 >= 0. If we deduct each element with mid (nums[i] -mid), the problem is transfered to find if there exists a subarray whoes sum >= 0. Since this is not strictly to find the maxSum, in better case if any subarray's sum >= 0, we terminate the search early and return true; in worst case we search all the subarray and find the maxmum sum, then check if maxSum >= 0.
Time complexity: O(nlogn)
Space complexity: O(1)
public class Solution {
private boolean containsAverageArray(List<Integer> nums, double targetAverage, int k) {
double sum = 0;
for(int i = 0; i < k; ++i) {
sum += nums.get(i) - targetAverage;
}
if(sum >= 0) return true;
double previousSum = 0;
double minPreviousSum = 0;
double maxSum = -Double.MAX_VALUE;
for(int i = k; i < nums.size(); ++i) {
sum += nums.get(i) - targetAverage;
previousSum += nums.get(i-k) - targetAverage;
minPreviousSum = Math.min(minPreviousSum, previousSum);
maxSum = Math.max(maxSum, sum - minPreviousSum);
if (maxSum >= 0) {
return true;
}
}
return false;
}
public double findMaxAverage(List<Integer> nums, int k) {
double minItem = Collections.min(nums);
double maxItem = Collections.max(nums);
while(maxItem - minItem >= 1e-5 ) {
double mid = minItem + (maxItem - minItem)/2.0;
boolean contains = containsAverageArray(nums, mid, k);
if (contains) {
minItem = mid;
}
else {
maxItem = mid;
}
}
return maxItem;
}
}
We can reduce one variable, maxSum, terminate if sum - minPrevious >= 0, sum - minPreviousSum is the maxSum ended at current index.
a. sum - minPrevious < 0 if maxSum > sum - minPrevious, maxSum < 0 in previous check
b. sum - minPrevious < 0 if maxSum < sum -minPrevious < 0
c. sum - minPrevious > 0 if maxSum < 0 < sum - minPrevious
public class Solution {
private boolean containsAverageArray(List<Integer> nums, double targetAverage, int k) {
double sum = 0;
for(int i = 0; i < k; ++i) {
sum += nums.get(i) - targetAverage;
}
if(sum >= 0) return true;
double previousSum = 0;
double minPreviousSum = 0;
for(int i = k; i < nums.size(); ++i) {
sum += nums.get(i) - targetAverage;
previousSum += nums.get(i-k) - targetAverage;
minPreviousSum = Math.min(minPreviousSum, previousSum);
if(sum >= minPreviousSum ) {
return true;
}
}
return false;
}
public double findMaxAverage(List<Integer> nums, int k) {
double minItem = Collections.min(nums);
double maxItem = Collections.max(nums);
while(maxItem - minItem >= 1e-5 ) {
double mid = minItem + (maxItem - minItem)/2.0;
boolean contains = containsAverageArray(nums, mid, k);
if (contains) {
minItem = mid;
}
else {
maxItem = mid;
}
}
return maxItem;
}
}
Idea 3. There is a O(n) solution listed on this paper section 3 (To read maybe)
https://arxiv.org/pdf/cs/0311020.pdf