Maximum Average Subsequence — Problem Statement & Solution Guide
Problem Description
Given an array of integers values and an integer windowSize, find the maximum average value over any subsequence of windowSize consecutive elements. Return the maximum average multiplied by 100000, rounded down to the nearest integer.
Examples
Input
[3, 4, 5], 3
Output
400000
Explanation: Step-by-step: with input [3, 4, 5] and windowSize 3, we calculate the average of the subsequence [3, 4, 5] as (3 + 4 + 5) / 3 = 4, then multiply by 100000 to get 400000, which is already rounded down.
Input
[20, 30], 2
Output
2500000
Explanation: Step-by-step: with input [20, 30] and windowSize 2, we calculate the average of the subsequence [20, 30] as (20 + 30) / 2 = 25, then multiply by 100000 to get 2500000, which is already rounded down.
Constraints
- 1 <= k <= n <= 10^5
- -10^4 <= arr[i] <= 10^4
Optimal Approach & Strategy
Fixed size sliding window. Calculate initial window sum. Slide one by one, update max sum. Finally return max_sum * 100000 / k. Time O(N), Space O(1).
Brute Force Approach
Calculate sum for every k-length subarray. Time O(N*K).
Verified Code Solutions
function solution(values, windowSize) {
let maxAverage = -Infinity;
for (let i = 0; i <= values.length - windowSize; i++) {
let sum = 0;
for (let j = i; j < i + windowSize; j++) {
sum += values[j];
}
let average = sum / windowSize;
maxAverage = Math.max(maxAverage, average);
}
return Math.floor(maxAverage * 100000);
}class Solution {
public:
int solution(vector<int>& values, int windowSize) {
double maxAverage = numeric_limits<double>::lowest();
for (int i = 0; i <= values.size() - windowSize; i++) {
double sum = 0;
for (int j = i; j < i + windowSize; j++) {
sum += values[j];
}
double average = sum / windowSize;
maxAverage = max(maxAverage, average);
}
return (int) (maxAverage * 100000);
}
};class Solution {
public int solution(int[] values, int windowSize) {
double maxAverage = Double.NEGATIVE_INFINITY;
for (int i = 0; i <= values.length - windowSize; i++) {
double sum = 0;
for (int j = i; j < i + windowSize; j++) {
sum += values[j];
}
double average = sum / windowSize;
maxAverage = Math.max(maxAverage, average);
}
return (int) (maxAverage * 100000);
}
}def solution(values, windowSize):
max_average = float('-inf')
for i in range(len(values) - windowSize + 1):
subsequence = values[i:i + windowSize]
average = sum(subsequence) / windowSize
max_average = max(max_average, average)
return int(max_average * 100000)function solution(values, windowSize) {
let maxAverage = -Infinity;
for (let i = 0; i <= values.length - windowSize; i++) {
let sum = 0;
for (let j = i; j < i + windowSize; j++) {
sum += values[j];
}
let average = sum / windowSize;
maxAverage = Math.max(maxAverage, average);
}
return Math.floor(maxAverage * 100000);
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.