Given an array that has n integers, find a sub array of given length k that has the maximum average value. Write a function that outputs the maximum average value.
Given an array consisting of n integers, find the contiguous subarray of given length 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: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
Note:1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].
The Naive Solution
The following JavaScript solution is a naive implementation searching for the maximum average however the sub array sum is calculated fresh every iteration.
The edge cases when the size of the array is 0 or 1 should be handled with care. The problem of below solution is that when the K is relative large, roughly half size of the size of the array n, the complexity is O(N^2).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | /** * @param {number[]} nums * @param {number} k * @return {number} */ var findMaxAverage = function(nums, k) { if (nums.length == 0) return 0; if (nums.length == 1) return nums[0]; // compute the first average let avg = nums.slice(0, k).reduce((a, b) => a + b, 0) / k; for (let i = 1; i + k <= nums.length; ++ i) { // compute the next possibilities let v = nums.slice(i, i + k).reduce((a, b) => a + b, 0 ) / k; // update the maximum avg = Math.max(avg, v); } return avg; }; |
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findMaxAverage = function(nums, k) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
// compute the first average
let avg = nums.slice(0, k).reduce((a, b) => a + b, 0) / k;
for (let i = 1; i + k <= nums.length; ++ i) {
// compute the next possibilities
let v = nums.slice(i, i + k).reduce((a, b) => a + b, 0 ) / k;
// update the maximum
avg = Math.max(avg, v);
}
return avg;
};Slide Window to Compute the Maximum Average Subarray
The above solution is slow because the sub array sum is calculated over and over again but this is not necessary as we move along the array, we can update the sum by subtracting previous one and add a new element to the right.
The following JavaScript implementation demonstrates the idea. The complexity is reduced to O(N).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | ** * @param {number[]} nums * @param {number} k * @return {number} */ var findMaxAverage = function(nums, k) { if (nums.length == 0) return 0; if (nums.length == 1) return nums[0]; let v = nums.slice(0, k).reduce((a, b) => a + b, 0); let cursum = v; for (let i = 1; i + k <= nums.length; ++ i) { cursum = cursum - nums[i - 1] + nums[i + k - 1]; v = Math.max(cursum, v); } return v / k; }; |
**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findMaxAverage = function(nums, k) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
let v = nums.slice(0, k).reduce((a, b) => a + b, 0);
let cursum = v;
for (let i = 1; i + k <= nums.length; ++ i) {
cursum = cursum - nums[i - 1] + nums[i + k - 1];
v = Math.max(cursum, v);
}
return v / k;
};The Java does not have a very nice and elegant slice function and hence, we can use a simple loop at the beginning to compute the first K items.
It is also observed that we don’t need to compute the average every iteration, but computing the maximum sum and divide it by K at the end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public double findMaxAverage(int[] nums, int k) { if (nums.length == 0) return 0; if (nums.length == 1) return nums[0]; double sum = 0; k = Math.min(k, nums.length); for (int i = 0; i < k; ++ i) { sum += nums[i]; } double v = sum; for (int i = 1; i + k <= nums.length; ++ i) { sum = sum - nums[i - 1] + nums[i + k - 1]; v = Math.max(v, sum); } return v / k; } } |
class Solution {
public double findMaxAverage(int[] nums, int k) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
double sum = 0;
k = Math.min(k, nums.length);
for (int i = 0; i < k; ++ i) {
sum += nums[i];
}
double v = sum;
for (int i = 1; i + k <= nums.length; ++ i) {
sum = sum - nums[i - 1] + nums[i + k - 1];
v = Math.max(v, sum);
}
return v / k;
}
}The C++ solution is quite similar except that we use std::min and std::max from the algorithm header.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <algorithm> class Solution { public: double findMaxAverage(vector<int>& nums, int k) { if (nums.size() == 0) return 0; if (nums.size() == 1) return nums[0]; double sum = 0; k = std::min(k, (int)nums.size()); for (int i = 0; i < k; ++ i) { sum += nums[i]; } double v = sum; for (int i = 1; i + k <= nums.size(); ++ i) { sum = sum - nums[i - 1] + nums[i + k - 1]; v = std::max(v, sum); } return v / k; } }; |
#include <algorithm>
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
double sum = 0;
k = std::min(k, (int)nums.size());
for (int i = 0; i < k; ++ i) {
sum += nums[i];
}
double v = sum;
for (int i = 1; i + k <= nums.size(); ++ i) {
sum = sum - nums[i - 1] + nums[i + k - 1];
v = std::max(v, sum);
}
return v / k;
}
};–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Binary Search Algorithm in Java
Next Post: You need a Numeric Keypad to Start with Your HHKB!
