Just another Divide-And-Conquer question - but somehow different 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)
Your solution doesn't work since it could output $i_2,j_1$ which isn't legal since $i_2 &gt; j_1$. Your code also has a few bugs &mdash; 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:


Buy and sell within the first half.
Buy and sell within the second half.
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.