[Solved]: Just another Divide-And-Conquer question - but somehow different

Problem Detail: 

Please consider the following Divide-And-Conquer 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.)

There already is a discussion about the same problem, but I don't understand why they try to make it that complicated. I think the following Algorithm will yield the result they ask for:

DivideAndConquer(1,..,n) (i1,j1) := DivideAndConquer(1,..,n/2) (i2,j2) := DivideAndConquer(n/2 + 1,..,n) return (min(p(i1),pi2),max(p(j1),p(j2))) 

Even if they ask for the range, we can get it from (i,j) := DivideAndConquer(1,..,n) by j-i. So, what am I missing?

PS: I don't see the point of using a DivideAndConquer approch at all. Why not sorting the input twice. Once in ascending and once in descending order induced by p(i).

EDIT: According to the explanation of Yuval Filmus, the algorithm should look like the following:

DivideAndConquer(1,..,n) (i1,j1) := DivideAndConquer(1,..,n/2) (i2,j2) := DivideAndConquer(n/2 + 1,..,n) Let p(i) be minimal in 1,..,n/2 Let p(j) be maximal in n/2 + 1,..,n return (i,j) 

Asked By : 0xbadf00d

Answered By : Yuval Filmus

Your solution doesn't work since it could output $i_2,j_1$ which isn't legal since $i_2 > j_1$. Your code also has a few bugs — are you returning indices or stock prices?

The idea behind the divide and conquer solution is that the optimal solution is of one of three forms:

1. Buy and sell within the first half.
2. Buy and sell within the second half.
3. Buy within the first half and sell within the second half.

The first two are taken care of by the recursion, and for the third you just need to compute the minimum of the first half and the maximum of the second half.

There is also a simple (and faster) solution not involving any kind of recursion or sorting. The idea is to scan the array from left to right, keeping at any given point the smallest value seen so far. At any given point in time, you can consider the gain from buying at the smallest price seen so far and selling at the current price. The maximum over all these possibilities is the optimal strategy. This algorithm takes linear time, and can even be implemented online.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24195