[Followups set to comp.programming]
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)
