Source code online books for professionals by professionals

hOW FaSt CaN We FIND a CONVeX hULL?
the divide-and-conquer solution has a running time of O(n lgn). there are lots of algorithms for finding convex 
hulls, some asymptotically faster, with running times as low as O(n lgh), where h is the number of points on the 
hull. in the worst case, of course, all objects will fall on the hull, and we’re back to 
Q(n lgn). in fact, this is the best 
time possible, in the worst case—but how can we know that?
We can use the idea from Chapter 4, where we show hardness through reduction. We already know from the 
discussion earlier in this chapter that sorting real numbers is 
W(n lgn), in the worst case. this is independent of 
what algorithm you use; you simply can’t do better. it’s impossible.
now, observe that sorting can be reduced to the convex hull problem. if you want to sort n real numbers, you 
simply use the numbers as x-coordinates and add y-coordinates to them that place them on a gentle curve. For 
example, you could have y = x
2
. if you then find a convex hull for this point set, the values will lie in sorted order 
on it, and you can find the sorting by traversing its edges. this reduction will in itself take only linear time.
imagine, for a moment, that you have a convex hull algorithm that is better than loglinear. by using the linear 
reduction, you subsequently have a sorting algorithm that is better than loglinear. but that’s impossible! in other 
words, because there exists a simple (here, linear) reduction from sorting to finding a convex hull, the latter 
problem is at least as hard as the former. So ... loglinear is the best we can do.
Greatest Slice
Here’s the last example: You have a sequence A containing real numbers, and you want to find a slice (or segment) 
A[i:j] so that sum(A[i:j]) is maximized. You can’t just pick the entire sequence, because there may be negative 
numbers in there as well.
15
 This problem is sometimes presented in the context of stock trading—the sequence 
contains changes in stock prices, and you want to find the interval that will give you the greatest profit. Of course, this 
presentation is a bit flawed, because it requires you to know all the movement of the stock beforehand.
An obvious solution would be something like the following (where n=len(A)):
 
result = max((A[i:j] for i in range(n) for j in range(i+1,n+1)), key=sum)
 
The two for clauses in the generator expression simply step through every legal start and end point, and we then 
take the maximum, using the sum of A[i:j] as the criterion (key). This solution might score “cleverness” points for  
its concision, but it’s not really that clever. It’s a naïve brute-force solution, and its running time is cubic (that is, Q(n
3
))! 
In other words, it’s really bad.
15
I’m still assuming that we want a nonempty interval. If it turns out to have a negative sum, you could always use an empty  
interval instead.

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
131
It might not be immediately apparent how we can avoid the two explicit for loops, but let’s start by trying to avoid 
the one hiding in sum. One way to do this would be to consider all intervals of length k in one iteration, then move to 
k+1, and so on. This would still give us a quadratic number of intervals to check, but we could use a trick to make the 
scan cost linear: We calculate the sum for the first interval as normal, but each time the interval is shifted one position 
to the right, we simply subtract the element that now falls outside it, and we add the new element:
 
best = A[0]
for size in range(1,n+1):
    cur = sum(A[:size])
    for i in range(n-size):
        cur += A[i+size] - A[i]
        best = max(best, cur)
 
That’s not a lot better, but at least now we’re down to a quadratic running time. There’s no reason to quit here, 
though.
Let’s see what a little divide and conquer can buy us. When you know what to look for, the algorithm—or at least 
a rough outline—almost writes itself: Divide the sequence in two, find the greatest slice in either half (recursively), 
and then see whether there’s a greater one straddling the middle (as in the closest point example). In other words, 
the only thing that requires creative problem solving is finding the greatest slice straddling the middle. We can reduce 
that even further—that slice will necessarily consist of the greatest slice extending from the middle to the left and the 
greatest slice extending from the middle to the right. We can find these separately, in linear time, by simply traversing 
and summing from the middle in either direction.
Thus, we have our loglinear solution to the problem. Before leaving it entirely, though, I’ll point out that there is, 
in fact, a linear solution as well; see Exercise 6-18.