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

"Arthur J. O'Dwyer" wrote:
On Tue, 21 Mar 2006, CBFalconer wrote:
Mark P wrote:
CBFalconer wrote:

Take a look at the solve() function I posted elsethread. Same
basic idea, but I think much simpler. It is much like
maintaining a moving average, where all you need is the history
over the prior window.

Simpler, perhaps, but as far as I can tell, not correct.

Did you plug it into the maxsum driver I published earlier? Please
do so and tell me what you find inaccurate. It is O(N).

% ./a.out 4 2
161531* 51542* 173471* 49805
225013 is the solution

% ./a.out 6 4
161531* 51542* 173471* 49805* 90851 154485*
468612 is the solution

I assume the starred entries are supposed to be the selection? In
that case, since all the entries are positive, and assuming there's
no signed overflow, all the entries should be starred, every time.
Certainly the starred entries shouldn't be non-contiguous, as in
the second example above.

Your choice to use very large positive integers instead of a
mixture of small positive and negative integers may be partly to
blame. Also, it looks like the code for initializing the array
from a random seed is mixed up with the code for computing the
solution, which is icky. I still can't really tell what the code
is supposed to be doing.

The *s mark the point at which any candidate sum is found, i.e. the
last l items form the largest sum found so far. Entries prior to
the start are presumed 0. The last * marks the point at which the
solution sum was found.

The numbers are quite small when run on a machine with 16 bit
integers.

I just used rand to supply a stream of positive integers. Lacking
srand, it will always supply the same sequence on any given
machine. Then I used advance knowledge of the summing to ensure
that no integer overflow could occur.

The array, indexed modulo l, holds the last l entries, and removes
the earliest from the running sum before inserting the current
entry.

I thought it was quite transparent code. Maybe I am wrong in that
assumption.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>


.

Relevant Pages

  • Re: How to find the maximum sum of atleast L consecutive integersgivena sequence of N integers.
    ... I assume the starred entries are supposed to be the selection? ... last l items form the largest sum found so far. ... just created and listed the input stream, ...
    (comp.programming)
  • Re: Multiple Sheets and Columns
    ... Column E = values to sum ... Valko" wrote: ... Each Date has like 10 entries below before going to the next Date. ... I have a formula that gets all the totals in one bucket, ...
    (microsoft.public.excel.worksheet.functions)
  • RE: Mileage Claim Formula
    ... Total Expenses (Sum of the two Entries ... "johndavies" wrote: ...
    (microsoft.public.excel.newusers)
  • Re: Multiple Sheets and Columns
    ... closed, other days, we may get nothing (sum 0). ... Each Date has like 10 entries below before going to the next Date. ... Valko" wrote: ... *ALL* ranges must be the same size: ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Access Reports are evil - please help
    ... Is the error I get when I try to total the entries. ... I have always done this sort of calculations in Excel, ... > Do you get a wrong sum? ... > What is the EXACT control source? ...
    (microsoft.public.access.reports)
Loading