Subsequence with highest average

Question

Given a sequence of N nonnegative numbers, how to find efficiently the continuous subsequence of length at least L (L is in input) with the highest possible average (sum of elements in the subsequence divided by its length)?
Please no brute-force algorithms trying all options.

Example:
0,9,8,1,9,5,2,3
L=3

result: 9,8,1,9
average=6.75

Thanks for help.

Answer 1

I am not sure you can do better than N*L ... Maybe you could search on the internet, there are some forums with algorithms addict :)

Answer 2

It seems like you need it, maybe for class. What did you tried to do ?

Answer 3

I tried for each possible length K from L to 2*L-1 (longer subsequences can be divided into two parts) to find the sum and average of first K elements, then by adding K+1. element and subtracting first element find the sum and average of next K elements, and so on for all K consecutive elements, keeping the maximum average found.
But that's slow - complexity is O(N*L).

Answer 4

ok, thank you for trying to help