[Followups set to comp.programmin g]

11******@gmail. com 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[i] >= 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[i] < 0)

{

neg = 1;

}

else

{

sum += arr[i]; /* 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.)

--

Richard Heathfield

"Usenet is a strange place" - dmr 29/7/1999

http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)