Maximum Average Subsequence — Problem Statement & Solution Guide
Problem Description
Given an integer array values and a positive integer windowSize, identify the contiguous subarray of length windowSize whose elements have the greatest arithmetic mean. Return the floor of that maximum mean multiplied by 100000. Formally, let S be the sum of a subarray of length windowSize; the answer is ⌊(max S / windowSize) × 100000⌋. The algorithm must run in linear time relative to the array size.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Average Subsequence"
WHY DOES IT MATTER?
Sliding‑window is a fundamental pattern for any problem that requires aggregating over a fixed‑size contiguous segment, turning quadratic scans into linear passes and enabling real‑time analytics on streams.
OPTIMIZATION CHALLENGE
The key insight is that the sum of the next window can be derived from the current sum by subtracting the element that slides out and adding the new element that slides in, eliminating redundant work.
REAL-WORLD CONNECTION
Think of a moving sensor reading (e.g., temperature) where you constantly need the average of the last k measurements to trigger alerts; you update the sum as new readings arrive without recomputing the whole window.
During an interview, write the initial sum of the first window, then loop from index k to n‑1 updating the sum in‑place; keep a variable for the maximum sum seen so far and compute the final scaled answer after the loop.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for the maximum average of any contiguous subarray of a fixed length. A naïve solution would recompute the sum for each possible window, leading to O(n·k) time where n is the array length and k is windowSize. This quickly becomes infeasible for large n (up to 10^6 or more) because the repeated summations dominate runtime. The optimal paradigm is the sliding‑window technique: maintain the sum of the current window while moving one step at a time, subtracting the element that leaves the window and adding the new element that enters. Because each array element is added and removed exactly once, the total work is linear, O(n). The final answer requires the floor of the maximum average multiplied by 100 000, which can be computed safely using integer arithmetic to avoid floating‑point precision issues.
Interview Questions on This Problem
Q1How would you modify the sliding‑window solution if the window size were not fixed but you needed the subarray with the maximum average of any length?
You can use a binary search on the answer (the average) combined with prefix sums to check if a subarray with average ≥ mid exists in O(n) per check, yielding O(n·log range). This transforms the problem into a feasibility test for each candidate average.
Q2Why does using a double or float to compute the average risk precision errors in this problem, and how can you avoid them?
Multiplying the average by 100 000 and taking the floor requires exact integer results; floating‑point rounding can produce off‑by‑one errors. Instead, keep the window sum as a 64‑bit integer, compute (maxSum * 100000) / windowSize using integer division, which yields the correct floor value.
Q3In a distributed system where the array is sharded across multiple nodes, how could you compute the maximum average subarray of a given size?
Each node computes local window sums for windows fully contained within its shard and also shares the prefix and suffix sums of length windowSize‑1 with neighboring nodes. With these overlapping sums, nodes can evaluate windows that cross shard boundaries, and a final reduction picks the global maximum.
Examples
Input
values = [1,12,-5,-6,50,3], windowSize = 4
Output
1275000
Explanation: Window sums: (1+12-5-6)=2 → avg 0.5; (12-5-6+50)=51 → avg 12.75; (-5-6+50+3)=42 → avg 10.5. The largest average is 12.75. 12.75 × 100000 = 1 275 000; floor gives 1275000.
Input
values = [5,5,5,5], windowSize = 2
Output
500000
Explanation: Every length‑2 window sums to 10, average 5. 5 × 100000 = 500000; floor yields 500000.
Input
values = [-10,-20,-30,-40], windowSize = 3
Output
-2000000
Explanation: Window sums: (-10-20-30)=-60 → avg -20; (-20-30-40)=-90 → avg -30. The maximum average is -20. -20 × 100000 = -2000000; floor remains -2000000.
Constraints
- 1 <= values.length <= 100000
- 1 <= windowSize <= values.length
- -1000000000 <= values[i] <= 1000000000
- Time complexity O(n)
- Auxiliary space O(1)
Optimal Approach & Strategy
Use a sliding window to update the sum in O(1) per step, achieving O(n) total time.
Brute Force Approach
Re‑calculate the sum for every possible window of size k, leading to O(n·k) time.
Verified Code Solutions
function maxAverageSubsequence(values, windowSize) {
let cur = 0, best = -Infinity;
for (let i = 0; i < values.length; ++i) {
cur += values[i];
if (i >= windowSize) cur -= values[i - windowSize];
if (i >= windowSize - 1) best = Math.max(best, cur);
}
// integer division in JS via Math.trunc
return Math.trunc((best * 100000) / windowSize);
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx=0;
const n = input[idx++];
const values = input.slice(idx, idx+n); idx+=n;
const windowSize = input[idx++];
console.log(maxAverageSubsequence(values, windowSize).toString());#include <bits/stdc++.h>
using namespace std;
long long maxAverageSubsequence(const vector<int>& values, int windowSize) {
long long cur = 0, best = LLONG_MIN;
for (int i = 0; i < (int)values.size(); ++i) {
cur += values[i];
if (i >= windowSize) cur -= values[i - windowSize];
if (i >= windowSize - 1) best = max(best, cur);
}
// floor((best / windowSize) * 100000) = (best * 100000) / windowSize using integer division
return (best * 100000LL) / windowSize;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> values(n);
for(int i=0;i<n;++i) cin>>values[i];
int windowSize; cin>>windowSize;
cout<<maxAverageSubsequence(values,windowSize)<<"\n";
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
public static long maxAverageSubsequence(int[] values, int windowSize) {
long cur = 0, best = Long.MIN_VALUE;
for (int i = 0; i < values.length; i++) {
cur += values[i];
if (i >= windowSize) cur -= values[i - windowSize];
if (i >= windowSize - 1) best = Math.max(best, cur);
}
return (best * 100000L) / windowSize;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int[] values = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
values[i] = Integer.parseInt(st.nextToken());
}
int windowSize = Integer.parseInt(br.readLine().trim());
System.out.println(maxAverageSubsequence(values, windowSize));
}
}
import sys
def max_average_subsequence(values, windowSize):
cur = 0
best = -10**30
for i, v in enumerate(values):
cur += v
if i >= windowSize:
cur -= values[i - windowSize]
if i >= windowSize - 1:
if cur > best:
best = cur
return (best * 100000) // windowSize
if __name__ == "__main__":
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
sys.exit(0)
n = data[0]
values = data[1:1+n]
windowSize = data[1+n]
print(max_average_subsequence(values, windowSize))
function maxAverageSubsequence(values, windowSize) {
let cur = 0, best = -Infinity;
for (let i = 0; i < values.length; ++i) {
cur += values[i];
if (i >= windowSize) cur -= values[i - windowSize];
if (i >= windowSize - 1) best = Math.max(best, cur);
}
// integer division in JS via Math.trunc
return Math.trunc((best * 100000) / windowSize);
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let idx=0;
const n = input[idx++];
const values = input.slice(idx, idx+n); idx+=n;
const windowSize = input[idx++];
console.log(maxAverageSubsequence(values, windowSize).toString());
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.