Stock Prices
February 14, 2017
Let’s begin with some sample data; the maximum occurs when you buy at 65 and sell at 150:
(define xs '(100 80 70 65 95 120 150 75 95 100 110 120 90 80 85 90))
The obvious solution is to compute all possible buy/sell pairs:
(define (buy-sell-quadratic xs)
(let ((buy 0) (sell 0))
(do ((xs xs (cdr xs))) ((null? xs) (values buy sell))
(do ((ys (cdr xs) (cdr ys))) ((null? ys))
(let ((diff (- (car ys) (car xs))))
(when (< (- sell buy) diff)
(set! buy (car xs)) (set! sell (car ys))))))))
> (buy-sell-quadratic xs) 65 150
That takes quadratic time. A better solution is a divide-and-conquer algorithm; split the array in two, then the solution is either in the first half of the array, or in the second half of the array, or is the low point of the first half and the high point of the second half. That takes time O(n log n) and space O(log n) for the recursion stack. We won’t write that code, because I always manage to get it wrong, and because there’s a still better solution.
The best solution is a linear scan over the input. We keep track of two values; the minimum value seen so far, which is initially the first value in the list, and the maximum profit, which is initially zero. Then at each step we make two computations;
(define (buy-sell-linear xs)
(let ((buy (car xs)) (profit 0))
(do ((xs (cdr xs) (cdr xs)))
((null? xs) (values buy (+ profit buy)))
(set! buy (min (car xs) buy))
(set! profit (max (- (car xs) buy) profit)))))
> (buy-sell-linear xs) 65 150
To test our program, we generate a thousand sample cases and compare the results of the two algorithms:
> (do ((k 1000 (- k 1))) ((zero? k))
(let ((xs (take 20 (shuffle (range 1000)))))
(assert
(call-with-values
(lambda () (buy-sell-linear xs))
(lambda (buy sell) (- sell buy)))
(call-with-values
(lambda () (buy-sell-quadratic xs))
(lambda (buy sell) (- sell buy))))))
That will produce no output. You can run the program at http://ideone.com/R8ukSG, where you will also see the contributions from the Standard Prelude.
This exercise is a twist on the maxumum sum subsequence problem that we studied in a previous exercise. All you have to do is preprocess the input to a list of differences from one day to the next, then find the maximum sum subsequence.
EDIT: Thomas kindly pointed out in a comment below that I incorrectly reset the buy price when it was below the current minimum buy price, even when the new buy price didn’t lead to a new maximum difference. Here is the corrected code, which you can run at http://ideone.com/UvcdJ9:
(define (buy-sell xs)
(let loop ((xs (cdr xs)) (lo (car xs)) (hi (car xs))
(min-lo (car xs)) (max-d 0))
(if (null? xs) (values lo hi max-d)
(let* ((min-lo (if (< (car xs) min-lo) (car xs) min-lo))
(d (- (car xs) min-lo)))
(if (< max-d d)
(loop (cdr xs) min-lo (car xs) min-lo d)
(loop (cdr xs) lo hi min-lo max-d))))))
Programming Praxis 
In Python.
def optimal(rates): low, optvalue, optlow, opthigh = float('inf'), 0, None, None for curr in rates: if curr < low: low = curr elif curr - low > optvalue: optvalue, optlow, opthigh = curr - low, low, curr return optlow, opthighQuadratic Python, recommends a shortest interval of days.
from itertools import combinations def best(prices): '''Return the day (a 0-based index to prices) to buy, and the day to sell, to gain the most in the given days, in a shortest time. ''' def key(be): b, e = be return prices[e] - prices[b], b - e return max(combinations(range(len(prices)), 2), key = key)Another (linear) Python solution.
from itertools import accumulate, tee def optimal(rates): r1, r2 = tee(rates) lows = accumulate(r1, min) return max(zip(lows, r2), key=lambda x: x[1]-x[0])A divide and conquer version in Python.
def divide_and_conquer(rates): def opt(rates): n = len(rates) if n == 1: return 0, rates[0], rates[0] L, R = rates[:n//2], rates[n//2:] left, right = opt(L), opt(R) buymiddle, sellmiddle = min(L), max(R) middle = (max(0, sellmiddle - buymiddle), buymiddle, sellmiddle) return max(left, right, middle) return opt(rates)[1:] if rates else (None, None)Here is my implementation in Julia. Interestingly, it worked on the first attempt, so the problem was probably not as challenging as I thought…
function spa{T best
best = z
buy = i
sell = j
end
end
end
return best, buy, sell
end
One known limitation of this algo is that it is possible to have multiple cases that yield an optimum profit. This algo will only yield the first such solution, however.
Here is my solution again, since the form truncated it for some reason… (if the problem persists, maybe the website is up for some maintenance!)
function spa{T best
best = z
buy = i
sell = j
end
end
end
return best, buy, sell
end
Zack, try the sourcecode tags (square brackets) around the code, any lang attribute (lang=”text” works, lang=”python” adds funny colours). It’ll preserve indentation and it’ll take less-than, greater-than signs literally. See the HOWTO link on top of the page.
Your linear solution doesn’t work, and this problem can’t be solved in both linear time and space. To see the problem, add a new low price after the correct solution in the list. For example, given your test data, add a 64 somewhere after the 150. Buy at 65, sell at 150 is still the correct answer, but your linear algorithm will claim you should buy at 64 and sell at 149, which you cannot.
What you can do is to use an O(n log n) solution: when you find a new possible low price, scan ahead in the list to verify that there exists an element >= (+ buy profit). Alternatively, you could use an optimistic algorithm, and instead of scanning ahead, assume that your new low price will be valid but save a continuation to restart with the old buy price. If you reach the end of the list and never found a sell price to justify your buy price, backtrack to your continuation.
@Thomas: You are correct that my solution doesn’t work; it resets the minimum buy price when it shouldn’t. But there is a linear-time and constant-space solution:
(define (buy-sell xs) (let loop ((xs (cdr xs)) (lo (car xs)) (hi (car xs)) (min-lo (car xs)) (max-d 0)) (if (null? xs) (values lo hi max-d) (let* ((min-lo (if (< (car xs) min-lo) (car xs) min-lo)) (d (- (car xs) min-lo))) (if (< max-d d) (loop (cdr xs) min-lo (car xs) min-lo d) (loop (cdr xs) lo hi min-lo max-d)))))) You can see the program in action, with 64 added to the end of the list of stock prices, at http://ideone.com/UvcdJ9.A couple of solutions in Racket.