Algorithm

[116Rohan]

You're given an array containing both positive and negative integers
and required to find the sub-array with the largest sum (O(N) a la
KBL). Write a routine in C for the above

Any pointers on the above problem will help.
Wont sum of all positive numbers will be the largest sub-array?

 

[Michael Mair]

You're given an array containing both positive and negative integers
and required to find the sub-array with the largest sum (O(N) a la
KBL). Write a routine in C for the above

Any pointers on the above problem will help.
Wont sum of all positive numbers will be the largest sub-array?

This sounds more like a problem with terms. Let us rephrase it:

Given A, an array N of signed long, find one index pair (i1, i2)
such that
signed long subsum = 0;
size_t i;

for (i = i1; i < i2; i++)
sum += A;
yields the maximal subsum possible for 0<=i1<i2<=N.
Note: You may have to use another type for subsum if the sum
becomes too large.

I do not know what "KBL" is supposed to mean.
If you do not either, start with the following:
- write a function to maximise subsum for a given index pair by
only removing entries from the start and end of the subarray
that diminish the sum, that is: increase/decrease the indices
- think how you can increase the subsum by other analyses.
- how can "splitting" a subarray help.

For more algorithm questions, ask in comp.programming; for problems
when writing your programme, come here.
Be sure to read
http://clc-wiki.net/wiki/Introduction_to_comp.lang.c
first.


Cheers
Michael

 

[Nick Keighley]

You're given an array containing both positive and negative integers
and required to find the sub-array with the largest sum (O(N) a la
KBL). Write a routine in C for the above

Any pointers on the above problem will help.
Wont sum of all positive numbers will be the largest sub-array?

I assume a "sub-array" has to be contiguous.

3 3 -1 3

The sub-array with the largest sum is the entire array

 

[Sensei]

I assume a "sub-array" has to be contiguous.

3 3 -1 3

The sub-array with the largest sum is the entire array

Not always (e.g. +3 +3 +3 +3 +3 -3 -3 -3 -3 -3), and this is OT,
nothing related to C.

 

[Richard Heathfield]

[Followups set to comp.programming]

(e-mail address removed) said:

You're given an array containing both positive and negative integers
and required to find the sub-array with the largest sum (O(N) a la
KBL). Write a routine in C for the above

Any pointers on the above problem will help.
Wont sum of all positive numbers will be the largest sub-array?

No, because they might not be contiguous.

Consider 1, -3, 2. The sub-arrays are:

1, -3, 2 : sum is 0
1, -3 : sum is -2
1 : sum is 1
-3, 2 : sum is -1
-3 : sum is -3
2 : sum is 2

So in this case, the largest sub-array does not include one of the positive
numbers.

Here's a possible approach to your problem which would be an O(N) solution -
comments welcomed.

You know that your array will consist of zero or more groups of one or more
positive (or rather, non-negative) numbers, and zero or more groups of one
or more negative numbers.

Firstly, we can ignore leftmost and rightmost negative values (unless the
entire array is filled with negative values, in which case the solution is
the single least negative value. For simplicity, that solution can easily
be determined in a single separate pass. (Remember that we can have as many
passes as we like and still retain O(N) behaviour, provided that the number
of passes does not depend on any variable, such as N).

sum = INT_MIN; /* or LONG_MIN, or whatever you're using */
nonneg = 0;
for(i = 0; !nonneg && i < lim; i++)
{
if(arr >= 0)
{
nonneg = 1;
}
else if(nonneg > sum)
{
sum = nonneg;
left = i;
right = i;
}
}

If the array is filled with non-negative values, the solution is the whole
array. Again, this can be determined in a single pass:

sum = 0;
neg = 0;
for(i = 0; !neg && i < lim; i++)
{
if(arr < 0)
{
neg = 1;
}
else
{
sum += arr; /* beware overflow, obviously */
}
}

if(!neg)
{
left = 0;
right = lim - 1;
}

So setting those aside as solved problems, we tackle the case where we have
at least one non-negative value. (I may slip, and say "positive" when I
mean "non-negative" - clearly, a 0 value can be added to any sub-array
without diminishing its value, so for the rest of this thread I will allow
myself to be a little sloppy with the term "positive".)

As I said above, we can ignore all the negative values on the left and right
of the array, so let's pretend they're not there.

We now have a setup like this:

A - B + C - D + E - F + (...)

where A, B, etc represent the magnitudes of contiguous positive and negative
number groups, alternately. At the beginning of the loop, these values are
not known.

We start off by summing A (and carefully recording its limiting indices).

Our tentative solution is [A] (by which I mean the subarray consisting
entirely of the A subarray).

We then sum B, again carefully recording its limits.

If B > A, then A - B will be negative, so there is no advantage to retaining
A (unless it is the only positive group, in which case it is, of course,
the solution); A and B between them effectively form a leftmost negative
group, so they can be discarded, and we simply go round again.

If A >= B, though, then the whole subarray that includes A and B contributes
to (or at least does not detract from) a solution. So we can now accumulate
A, B, and C into a single subarray which we know will have a positive
value. That is, our tentative solution is now [A - B + C] - D + E - F +
(...)

Because [A - B + C] is effectively a single subarray, we are now in the same
position as before, i.e. alternating positive and negative subarrays, so we
simply go round again until we run out of data.

This method starts off by identifying and evaluating two subarrays, and then
identifies and evaluates each subsequent subarray in turn, either accreting
it or rejecting all the results so far, so it can be done in one linear
pass.

Writing the C code is left as a fairly trivial exercise. (The only mildly
tricky bit is making sure you don't overflow.)

 

[Nick Keighley]

Not always (e.g. +3 +3 +3 +3 +3 -3 -3 -3 -3 -3),

I meant "in this particular case". I was giving a counter example to
the
OPs claim.

and this is OT, nothing related to C.

yup

 

[Julian V. Noble]

You're given an array containing both positive and negative integers
and required to find the sub-array with the largest sum (O(N) a la
KBL). Write a routine in C for the above

Any pointers on the above problem will help.
Wont sum of all positive numbers will be the largest sub-array?

This problem is straight out of "Programming Pearls" or "More
Programming Pearls". Any serious programmer should own these.

 

[CBFalconer]

You're given an array containing both positive and negative integers
and required to find the sub-array with the largest sum (O(N) a la
KBL). Write a routine in C for the above

Any pointers on the above problem will help.
Wont sum of all positive numbers will be the largest sub-array?

Strictly speaking this is OT for c.l.c, but it came up in another
newsgroup a while ago, and I published this solution. I believe it
to be accurate, but have not proven so. Have at it.

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

/* Public Domain by CB Falconer, 2006-03-06 */

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

#define MAXRUN 100
typedef int (*instream)(void); /* how to get values */

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

void help(void)
{
fprintf(stderr, "Usage: maxsum <n> <l> [any]\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"
"\n[any] entry enables debug display\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 */

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

int column;

/* setting column < 0 inhibits all display */
void showitem(int item, int itemcnt)
{
if (column >= 0) {
if (!itemcnt) column += printf("%10d ", item);
else column += printf("%10d,%-2d", item, itemcnt);
if (column > 64) {
column = 0; putchar('\n');
}
}
} /* showitem */

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

size_t maxcount;
#define initnext(count) maxcount = count

/* get the next integer from the input stream */
int next(void)
{
int value;

if (!maxcount) return EOF;
else maxcount--;
do {
value = (rand() % 65) - 32; /* symettric about 0 */
} while (EOF == value);
return value;
} /* next */

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

/* A list of these items holds the pertinent input history */
struct sofar {
int sumtohere;
struct sofar *next;
};

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

struct sofar *discard(struct sofar *trail)
{
struct sofar *t;

t = trail->next;
free(trail);
return t;
} /* discard */

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

struct sofar *newitem(int value)
{
struct sofar *item;

if (!(item = malloc(sizeof *item))) {
fprintf(stderr, "Out of memory, halting\n");
exit(EXIT_FAILURE);
}
item->sumtohere = value;
item->next = NULL;
return item;
} /* newitem */

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

/* solve the real problem */
int solve(instream getnext, int l)
{
int v, items;
int sum, maxsum;
struct sofar *trail, *current, *temp;

/* initialize detection */
current = trail = newitem(0);
sum = maxsum = items = 0;

while (EOF != (v = getnext())) {
/* process v into the system */
items++;

temp = newitem(v + current->sumtohere);
current->next = temp;
current = temp;

while (trail->next->sumtohere <= trail->sumtohere
&& items > l) {
/* oldest input value is negative or zero so */
/* the sum can only be imcreased by discard */
trail = discard(trail);
items--;
}

sum = current->sumtohere - trail->sumtohere;
while ((sum <= 0) && (items > l)) {
/* The only purpose of the older entries is */
/* to enable inclusion of a future series */
/* without demanding the item count start */
/* from this current point. This may drive */
/* the sum more negative. The preceding */
/* while loop will eventually handle that */
trail = discard(trail);
items--;
sum = current->sumtohere - trail->sumtohere;
}

showitem(v, 0);
if ((sum >= maxsum) && (items >= l)) {
maxsum = sum;
showitem(sum, items);
}
}
return maxsum;
} /* solve */

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

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

if (argc < 3) help();
else {
if (3 == argc) column = -1; /* inhibit debug */
n = getint(argv[1]);
l = getint(argv[2]);
if (l > n) help();
initnext(n);

ans = solve(next, l);

if (column > 0) putchar('\n');
printf("Max. sum is %d\n", ans);
}
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/>