Re: How to find the maximum sum of atleast L consecutive integers given a sequence of N integers.

"vb@xxxxxxxxx" <vb.here@xxxxxxxxx> wrote in message
news:1142859607.458037.81030@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Hi all,

How can we find the maximum sum of atleast L consecutive integers given
a sequence of N integers.

The brute force approach of forming all possible length sequences at
every index and finding their sum gives an O(N^2) solution which is not
desirable.

Can somebody tell me a better approach for this ?


It can be calculated in O(N). See Robert Bentley's 'Programming Pearls' book
for more details.

There's a copy of the relevant chapter at:

http://www.student.cs.uwaterloo.ca/~cs134/Resources/read/Articles/Bentley/AlgorithmDesignTechniques.pdf

but I'd recommend the whole book. Think a bit more about the problem before
peeking!

--
Roger


.