Programming Pearls: finding sub-array with max sum

Question

Hi,

I was reading "programming pearls" book and stuck in some place. The (best) original solution for the problem (finding sub-array with max sum) is:

maxsofar = О 
maxendinghere = О 
for i = [0. n) 
{
   maxendinghere = max(maxendinghere + x[i], 0) 
   maxsofar = max(maxsofar, maxendinghere) 
}

Then the problems is changed as follows and the program is asked to be modified:

Instead of finding sub-array with maximum sum, we have to find sub-array with sum closest to zero (not minimum) or some other number f.

1. So I would solve this by just changing the function "max" to some function that will return the number which is closer to zero (or f).
2. maxsofar would be initialized to an element closest to zero (or f)

This solution runs in O(n), but the author is giving a solution that's difficult and runs in O(nlogn) and claims that this the optimum solution (the best possible theoretically).

Please could you point out an error in my solution (if book says nlogn is best, then my solution must have some errors).

UPDATE: So my answer will be:

closest = get_element_closest_to_zero(); 
maxsofar = closest;
maxendinghere = 0; 
for i = [0. n) 
{
   maxendinghere = closest_to_zero(maxendinghere + x[i], closest);
   maxsofar = closest_to_zero(maxsofar, maxendinghere) ;
}

Thanks.

Answer 1

Here's a counterexample.

[100, 2, -2, -50]

The correct answer is the sub array [2, -2]. However, since 100 + 2 - 2 == 100, and 100 + 2 - 2 - 50 = 50 and 50 is closer to 0, your algorithm will return [100, 2, -2, -50].

Answer 2

Counterexample: [30; -50; 45]

First you will pick the 30. Then when you get to the -50, maxendinghere will be -20 and maxsofar also -20. When you get to the 45, you will have maxendinghere = closest(-20 + 45 = 25, 30) = 25 and maxsofar will remain -20.

The correct answer however is -5: -50 + 45 = -5

Answer 3

What about the sequence [100, -201, 100]. That will give the initial conditions

closest = 100
maxsofar = 100
maxendinghere = 0

after 1 step

x[i] = 100
maxendinghere = closest_to_zero(100, 100)
maxsofar = 100

after 2 steps

x[i] = -201
maxendinghere = closest_to_zero(-101, 100)
maxsofar = 100

after 3 steps

x[i] = 100
maxendinghere = closest_to_zero(-101, 100)
maxsofar = 100

Answer 4

[1, 100, -100]

For this array, your algorithm will return [1], but the correct response should be [100, -100].