Re: How to find the maximum sum of atleast L consecutive integers given a sequence of N integers.
- From: Ben C <spamspam@xxxxxxxxx>
- Date: 20 Mar 2006 15:15:56 GMT
On 2006-03-20, vb@xxxxxxxxx <vb.here@xxxxxxxxx> wrote:
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.
Could you do something like this:
1. Create a new sequence by replacing each run of adjacent positive
integers with their sum and each run of adjacent negatives with their
sum. Also create some kind of index so that each member of the new
sequence can be mapped back to the start and end of the run it
represents in the original sequence.
2. Find the highest adjacent sum in the new (shorter) sequence
using your brute force method.
3. Using the index match this back to the original sequence. If the
length of this sequence is < L, go back to step 2 looking for the
next highest.
Just a thought, I haven't tried it.
.
- References:
- Prev by Date: Re: Have you ever considered of mousing ambidextrously?
- Next by Date: Re: How to find the maximum sum of atleast L consecutive integers given a sequence of N integers.
- Previous by thread: Re: How to find the maximum sum of atleast L consecutive integers given a sequence of N integers.
- Next by thread: Re: How to find the maximum sum of atleast L consecutive integers given a sequence of N integers.
- Index(es):
Relevant Pages
|
