Given an array consisting of
n
integers, find the contiguous subarray of given lengthk
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: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75Note:
- 1 <=
k
<=n
<= 30,000.- Elements of the given array will be in the range [-10,000, 10,000].
The naive solution is to consider every possible subarray with length equal to , and to find out the maximum average possible from out of these subarrays chosen.
Java
public class Solution { public double findMaxAverage(int[] nums, int k) { double res = Integer.MIN_VALUE; for (int s = 0; s < nums.length - k + 1; s++) { double sum = 0; for (int i = 0; i < k; i++) { sum += nums[i + s]; } res = Math.max(res, sum / k); } return res; } }
Complexity Analysis
Time complexity : . We traverse over subarrays of length for a total of times.
Space complexity : . Constant extra space is used.
Algorithm
We know that in order to obtain the averages of subarrays with length , we need to obtain the sum of these length subarrays. One of the methods of obtaining this sum is to make use of a cumulative sum array, , which is populated only once. Here, is used to store the sum of the elements of the given array from the first element upto the element at the index.
Once the array has been filled up, in order to find the sum of elements from the index to , all we need to do is to use: . Thus, now, by doing one more iteration over the array, we can determine the maximum average possible from the subarrays of length .
The following animation illustrates the process for a simple example.
!?!../Documents/643_Maximum_Average.json:1000,563!?!
Java
public class Solution { public double findMaxAverage(int[] nums, int k) { int[] sum = new int[nums.length]; sum[0] = nums[0]; for (int i = 1; i < nums.length; i++) sum[i] = sum[i - 1] + nums[i]; double res = sum[k - 1] * 1.0 / k; for (int i = k; i < nums.length; i++) { res = Math.max(res, (sum[i] - sum[i - k]) * 1.0 / k); } return res; } }
Complexity Analysis
Time complexity : . We iterate over the array of length once to fill the array. Then, we iterate over elements of to determine the required result.
Space complexity : . We make use of a array of length to store the cumulative sum.
Algorithm
Instead of creating a cumulative sum array first, and then traversing over it to determine the required sum, we can simply traverse over just once, and on the go keep on determining the sums possible for the subarrays of length . To understand the idea, assume that we already know the sum of elements from index to index , say it is .. Now, to determine the sum of elements from the index to the index , all we need to do is to subtract the element from and to add the element to . We can carry out our process based on this idea and determine the maximum possible average.
Java
public class Solution { public double findMaxAverage(int[] nums, int k) { double sum=0; for(int i=0;i<k;i++) sum+=nums[i]; double res=sum; for(int i=k;i<nums.length;i++){ sum+=nums[i]-nums[i-k]; res=Math.max(res,sum); } return res/k; } }
Complexity Analysis
Time complexity : . We iterate over the given array of length once only.
Space complexity : . Constant extra space is used.
Analysis written by: @vinod23