Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have some confusion related to a divide and conquer problem. Here is the problem

You’re consulting for a small computation-intensive investment company, and they have the following type of problem that they want to solve over and over. A typical instance of the problem is the following. They’re doing a simulation in which they look at n consecutive days of a given stock, at some point in the past. Let’s number the days i=1,2,...,n; for each day i, they have a price p(i) per share for the stock on that day. (We’ll assume for simplicity that the price was fixed during each day.) Suppose during this time period, they wanted to buy 1,000 shares on some day and sell all these shares on some (later) day. They want to know: When should they have bought and when should they have sold in order to have made as much money as possible? (If there was no way to make money during the n days, you should report this instead.)

For example, suppose n = 3, p(1) = 9, p(2) = 1, p(3) = 5. Then you should return “buy on 2, sell on 3” (buying on day 2 and selling on day 3 means they would have made $4 per share, the maximum possible for that period).

Clearly, there’s a simple algorithm that takes time $O(n^2)$: try all possible pairs of buy/sell days and see which makes them the most money. Your investment friends were hoping for something a little better.

Show how to find the correct numbers i and j in time O(n log n).

Solution We’ve seen a number of instances in this chapter where a brute- force search over pairs of elements can be reduced to O(n log n) by divide and conquer. Since we’re faced with a similar issue here, let’s think about how we might apply a divide-and-conquer strategy.

A natural approach would be to consider the first n/2 days and the final n/2 days separately, solving the problem recursively on each of these two sets, and then figure out how to get an overall solution from this in O(n) time. This would give us the usual recurrence T (n) ≤ 2T(n/2) + O(n), and hence O(n log n).

Also, to make things easier, we’ll make the usual assumption that n is a power of 2. This is no loss of generality: if n′ is the next power of 2 greater than n, we can set p(i) = p(n) for all i between n and n′. In this way, we do not change the answer, and we at most double the size of the input (which will not affect the O() notation).

Now, let S be the set of days 1,...,n/2, and S′ be the set of days n/2+ 1, . . . , n. Our divide-and-conquer algorithm will be based on the following observation: either there is an optimal solution in which the investors are holding the stock at the end of day n/2, or there isn’t. Now, if there isn’t, then the optimal solution is the better of the optimal solutions on the sets S and S′. If there is an optimal solution in which they hold the stock at the end of day n/2, then the value of this solution is p(j) − p(i) where i ∈ S and j ∈ S′. But this value is maximized by simply choosing i ∈ S which minimizes p(i), and choosing j ∈ S′ which maximizes p(j).

Thus our algorithm is to take the best of the following three possible solutions.

. The optimal solution on S.
. The optimal solution on S′.
. The maximum of p(j)−p(i), over i∈S and j∈S′.

The first two alternatives are computed in time T(n/2), each by recursion, and the third alternative is computed by finding the minimum in S and the maximum in S′, which takes time O(n). Thus the running time T(n) satisfies T(n) ≤ 2T(n/2) + O(n), as desired.

Can anyone explain whats going on here? I didn't get how this algorithm actually works. I know they are dividing the days into first half and second half. But I didn't get this part specially

Our divide-and-conquer algorithm will be based on the following observation: either there is an optimal solution in which the investors are holding the stock at the end of day n/2, or there isn’t. Now, if there isn’t, then the optimal solution is the better of the optimal solutions on the sets S and S′. If there is an optimal solution in which they hold the stock at the end of day n/2, then the value of this solution is p(j) − p(i) where i ∈ S and j ∈ S′. But this value is maximized by simply choosing i ∈ S which minimizes p(i), and choosing j ∈ S′ which maximizes p(j).

share|improve this question
    
You split the range in two parts. Either the best subrange is entirely in the first part, or in the second part, or it straddles the division point. The best subrange in the first two cases is determined recursively, the third case by scanning from the midpoint in both directions. –  vonbrand Feb 24 '13 at 11:19
    
@vonbrand. I didn't get it. Can you give me an example to clarify? –  user34790 Feb 24 '13 at 13:31
    
Let's say you want to know the best range in 1..20. Divide into subranges 1..10 and 11..20, compute the best of both ranges (say 3..5 gives 6 at the left, 14..16 gives 7 at the right). This would give the answer, but you also need to check if there is a better range crossing 10, like 8..13. –  vonbrand Feb 24 '13 at 15:15
    
@vonbrand. That I can understand. I didn't mean that. Particularly I am confused when they say. "either there is an optimal solution in which the investors are holding the stock at the end of day n/2, or there isn’t. " What is meant by saying that the investors are holding the stock at the end of day n/2 or there isn't. Why is it n/2? I didn't get what they are trying to say for this particular line. –  user34790 Feb 24 '13 at 15:20
    
Look at the example I gave: Either the best range is in the left half, in the right half, or it starts in the left half and ends in the right. The last case is when they are holding the stock at day 10, i.e., 20 / 2. –  vonbrand Feb 24 '13 at 15:24
show 1 more comment

1 Answer 1

What I'd have done is to scan the array of prices, keeping track of the best range seen so far and the best starting point for the range ending here. I.e., when standing at day $k$, know the best range before $k$ (say $i$ to $j$, and its value $b$; and keep track what $l$ is so that the range $l$ to $k$ is maximal, say $B$, and if $B$ is better than $b$ adjust things accordingly. Extend the range to $k + 1$, and repeat.). This algorithm is $O(n)$. But that's just me...

[This algorithm isn't original, it's from Bentley's "Programming Pearls", where a delicious story on a very similar problem (maximal subrange sum) is discussed from an $O(n^3)$ algorithm down to the given $O(n)$, passing through the $O(n \log n)$ algorithm sketched by OP.]

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.