2

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.

Improve this question
1
  • Would you mind cleaning up your pseudo code? I think you have a few typos in there such as maxCmaxendinghere. Commented Sep 21, 2010 at 19:20

4 Answers 4

Reset to default
4

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

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

You are right. To generalize the problem with my solution is that "being close to zero" does not have same properties as being "max", and this property has to do with line: max(maxendinghere + x[i], 0). I'm not able to formalize this "property" of being "max" right now, at midnight though. Thanks for pointing out.
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].

Improve this answer

2 Comments

100 + 2 - 2 and 100 + 2 - 2 - 50 never will be compared to each other. maxsofar is initialized to 2, then closest_to_zero(2, maxendinghere) will always return 2, except for the (2-2) case. Please review my above update. Am I missing some point?
Ah, I'm glad you clarified your code. Your first version of the question is ambiguous about f but I should have figured it out anyway. My fault.
0 
[1, 100, -100]

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

Improve this answer

Comments

0

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
Improve this answer

2 Comments

@Azho KG: Umm, no. 100 + -201 + 100 is 1, so the answer of 100 is not correct.
You are right. It was too late and I was sleepy - so missed the point.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.