# market timing

Write a function accepting a sequence of stock prices and returning a pair of dates such that the stock bought on the first date and sold on the second date produces the maximum return of all possible date pairs.

``` \$ cat mt.rkt
#lang racket

(define (linear-market-timer prices)

; Return a pair containing indices into the given price vector
; indicating the days on which to buy (car) and sell (cdr) a stock
; for maximum return.

(let*

((n (vector-length prices))
(n-1 (- n 1)))

(if (= n 0)

(raise-user-error 'linear-market-timer
"zero-length price vector given")

(let loop

(sell-i n-1) (min-i n-1) (max-i n-1) (best-return 0))

(cons min-i max-i)

(let*

(sell-p (vector-ref prices sell-i))

(cond

((< best-return return)

(#t
(loop next-buy-i sell-i min-i max-i best-return)))))))))

; Return a pair containing indices into the given price vector
; indicating the days on which to buy (car) and sell (cdr) a stock
; for maximum return.

(let*

((n (vector-length prices))
(n-1 (- n 1)))

(if (= n 0)
(raise-user-error 'linear-market-timer
"zero-length price vector given")

(let outer-loop ((i 0) (min-i 0) (max-i 0) (best-return 0))
(if (= i n-1)
(cons min-i max-i)
(let inner-loop

((j (+ i 1))
(min-i min-i) (max-i max-i) (best-return best-return))

(if (= j n)
(outer-loop (+ i 1) min-i max-i best-return)
(let ((return
(- (vector-ref prices j) (vector-ref prices i)))
(next-j (+ j 1)))
(if (< best-return return)
(inner-loop next-j i j return)
(inner-loop next-j min-i max-i best-return))))))))))

(require rackunit "utl.rkt")

(call-with-vector-permutations
(iota-vector 9)
(lambda (prices)
(let* ((return (lambda (p)
(- (vector-ref prices (cdr p)) (vector-ref prices (car p)))))
(r1 (return (linear-market-timer prices)))