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 ?

vb@gmail.com wrote:
) 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 ?

Your professor, probably. A usenet groups search would work as well.
A normal web search would also get plenty of results.

Or, you could give some more insight on how much you do know and if you've
got some idea on how to solve it and then maybe someone can give you a hint
so that you can work it out for yourself, which is much more fun in the end.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Well William,

First of all , i am not a student .. I was just solving these problems
out of fun and got stuck on this one .. So after thinking for some time
only I have asked for help..
And regarding searching the solution - yeah i have tried searching
usenet and web, but without any results. Would be great if you could
give a link instead of rebuking around ..

Willem wrote:

vb@gmail.com wrote:
) Well William,

Willem. I'm Dutch.

) First of all , i am not a student .. I was just solving these problems
) out of fun and got stuck on this one .. So after thinking for some time
) only I have asked for help..
) And regarding searching the solution - yeah i have tried searching
) usenet and web, but without any results. Would be great if you could
) give a link instead of rebuking around ..

Well if you're solving them for fun, you probably will want a hint
instead of a link to a complete solution, right ?

Here's a hint:

Draw the points of the array as a graph. Then, if you want the sum
from one point to another, draw two vertical lines at those points.
Now, doesn't that picture remind you of something, in a mathematical sense ?


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

"vb@gmail.com" wrote:

If you sort the integers the last L items are the biggest.

On 2006-03-20, vb@gmail.com <vb.here@gmail.com> wrote:
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.

"vb@gmail.com" <vb.here@gmail.com> wrote in message
news:1142859607.458037.81030@e56g2000cwe.googlegro ups.com...
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/~...Techniques.pdf

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

--
Roger

this is a program to find sum in o(N)

int maxSum(int a[])
{

int sumMax=0,thisSum=0;
int j;

for(j=0;j<sizeof(a);j++)
{

thisSum+=a[j];

if(thisSum>sumMax)
sumMax=thisSum;
else if(thisSum<0)
thisSum=0;
}
return(sumMax);
}






vb@gmail.com wrote:

sudharsan wrote:
) this is a program to find sum in o(N)
)
) int maxSum(int a[])
) {
)
) int sumMax=0,thisSum=0;
) int j;
)
) for(j=0;j<sizeof(a);j++)
) {
)
) thisSum+=a[j];
)
) if(thisSum>sumMax)
) sumMax=thisSum;
) else if(thisSum<0)
) thisSum=0;
) }
) return(sumMax);
) }

It's not very nice to give a complete solution to someone who's solving
programming problems for fun. You're taking away the fun.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

"vb@gmail.com" wrote:
Please don't top-post. Your answer belongs after, or intermixed
with, the material you quote after snipping portions not germane to
your reply.

On your assurance that this is not homework, which for some reason
I believe, here is a reply. There are various techniques, most of
which will involve keeping a selection of the previous 0 to l th
inputs. The most efficient will probably involve a priority queue,
built around a heap structure. You can research those phrases.

I have done the hard part and built you an outline, so all you need
to do is fool with the solve() function. I have also taken
precautions to ensure that the input data will not cause
overflows. You will need to define some more variables. Have fun.

/* How to find the maximum sum of at least L consecutive
integers given a sequence of N integers. */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAXRUN 100

/* -------------- */

void help(void)
{
fprintf(stderr, "Usage: maxsum <n> <l>\n"
"where n < %d and l < n\n"
"Finds maximum sum of at least l consecutive\n"
"integers in a sequence of n integers\n",
MAXRUN);
exit(EXIT_FAILURE);
} /* help */

/* -------------- */

int getint(char *s)
{
long test;
char *endptr;

test = strtol(s, &endptr, 10);
if ((test > MAXRUN) || (test <= 0)) help(); /* and exit */
return test;
} /* getint */

/* -------------- */

void solve(int n, int l)
{
int i, v, column;

column = 0;
for (i = 0; i < n; i++) {
v = rand() % (INT_MAX / (MAXRUN+1));
column += printf("%10d", v);
if (column > 64) {
putchar('\n');
column = 0;
}
/* now process v into the system */
}
if (column) putchar('\n');

/* now display the solution */
puts("is the solution");
} /* solve */

/* -------------- */

int main(int argc, char **argv)
{
int n, l;

if (argc < 3) help();
else {
n = getint(argv[1]);
l = getint(argv[2]);
if (l > n) help();
solve(n, l);
}
return 0;
} /* main */

--
"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/>

CBFalconer wrote:
Huh, what makes you think a priority queue is relevant here?

On Mon, 20 Mar 2006, Willem wrote:
"sudharsan" didn't give a complete solution. He(?) didn't even give a
partial solution, IMO, since what he(?) typed is partly wrong and partly
trivial.
The lack of indentation in the code is a major clue that "sudharsan"
is clueless. The refusal to use capital letters or punctuation is another.
The confusion of arrays and pointers in line 7 (the 'for' loop) is
another. But the most obvious mistake is that "sudharsan"'s post never
makes use of the OP's parameter 'L' at all! So how could it possibly be
correct?

Anyway, someone posted a link to a book that reportedly has the
solution; I haven't peeked yet.

-Arthur

Googmeister wrote:
I didn't think it all out, but to form a maximal sum you need to
collect a maximal string of a certain length. A priority queue can
do this, since you can always detect if the next value will
increase the total. However, I missed the 'consecutive' part of
the specification, so a simple array and running total would do as
well. The priority queue would allow extracting a maximal sum of
any l items in the n inputs.

At any rate, I left the implementation to the OP :-)

--
"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/>

CBFalconer wrote:
A preemptive strike against top posting to the OP? It's tough to NOT
post at the top when you're the first!

--
Thad

Thad Smith wrote:
Nope, he had already committed the top-posting sin in another reply
in the thread.

--
"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/>

vb@gmail.com wrote:
Here's an O(N) approach I've come up with which I believe works:

Let the set of integers be: a_1 a_2 ... a_N

Compute the sequence of partial sums A, where A_i = a_1 + a_2 + ... +
a_i and, as a special case, A_0 = 0. This sequence can be computed in
time O(N).

Compute the sequence of partial minima M, where M_i = min {A_j} where 0
<= j <= i. This sequence can also be computed in time O(N).

The desired result is equivalent to finding the maximum of A_j - A_i
over all i,j such that j - i >= L and i >= 0.

For any *fixed* j, this is in turn equivalent to finding the minimum of
A_i for i <= j - L which is exactly M_(j-L).

Thus the desired result is the maximum of A_j - M_(j-L) over j >= L.
This too can be computed in O(N), hence the entire algorithm is linear.

Hope that helps,
Mark Pilloff

In article <XlPTf.2445$4L1.2418@newssvr11.news.prodigy.com> ,
usenet@fall2005REMOVE.fastmailCAPS.fm says...
Neat!

- Gerry Quinn

CBFalconer wrote:
.... snip code ...

Now that the OP has had a chance to digest that, here is a revision
to the solve stub that fills his need:

void solve(int n, int l)
{
int i, v, column;
int subrun[MAXRUN]; /* only first l used */
int ix; /* index to subrun */
int sum, maxsum; /* within subrun */

/* initialize detection */
sum = maxsum = ix = 0;
for (i = 0; i < l; i++) subrun[i] = 0;

column = 0;
for (i = 0; i < n; i++) {
v = rand() % (INT_MAX / (MAXRUN+1));
column += printf("%10d", v);

/* now process v into the system */
sum -= subrun[ix]; sum += v; subrun[ix] = v;
ix = (ix + 1) % l;
if (sum <= maxsum) putchar(' ');
else { /* mark new value */
maxsum = sum; putchar('*');
}

if (++column > 64) { /* wrap display */
putchar('\n'); column = 0;
}
}
if (column) putchar('\n');

/* now display the solution */
printf("%d is the solution\n", maxsum);
} /* solve */

--
"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/>

Mark P 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.

A variant, involving heaps or priority queues, can find the maximum
or minimum sum of any l items within the n samples.

--
"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/>

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

Mark