dynamicprogramming_stock.py

"""
Given a sequence of stock prices, what are the 2 values to buy and sell such that loss is maximized?
"""

prices = [[1,6,0,4,9,0,10],
          [1,2,3,4,5,6,7,8],
          [15,1,2,3,4,5,6,7,0],
          [7,3,9,5,2,1,4,14,16,17],
          [291, 592, 116, 480, 861, 438, 333, 541, 505, 272],
          [25, 679, 1, 493, 593, 579, 943, 258, 104, 997]]

          
# Naive solution: O(n^2)
def naive_solve(p):
  ans={}
  diff = None # Should be least
  for i in range(0,len(p)):
    buy = p[i]
    for j in range(0,len(p)):
      sell = p[j]
      if (i<j):
        if diff==None:
          diff = buy - sell
        elif (buy-sell)>diff:
          diff = buy - sell
          #print "Max loss of :", diff, ". Bought on day ", i, " at price ", buy, " and sold on day ", j, " at price ", sell
          ans[diff] = {"Bought at price ":buy, "Bought on day":i, "Sold at price" : sell, "Sold on day " : j, "Loss of" : diff}
  if (len(ans.keys())>0):
    print ans[max(ans.keys())]
  else:
    print "Always a profit"

def test_naive_solve():
  for p in prices:
    naive_solve(p)
  print "\n\n\n"

# Improved solution
def solve2(p):
  maxb = None
  mins = None
  diffs = {}

  # Init
  maxb = p[0]
  mins = p[0]
  diffs[(maxb,mins)] = maxb-mins

  for cur in range(1, len(p)):
    if (p[cur]<mins):
      mins=p[cur]
    if (p[cur]>maxb):
      maxb = p[cur]
      mins = p[cur]
    diffs[(maxb, mins)] = maxb-mins
  print diffs
  return max(diffs.values())

def test_dp_solve():
  for p2 in prices:
    print p2
    print "Max loss: ", solve2(p2)
    print "---------"

test_naive_solve()
test_dp_solve()


large = [random.randrange(0,10000) for i in range(0,10000)]
# Edit out 2 values to be 99999 and 0, which is the correct answer

#naive_solve(large)
"""
Interrupted after,
real  0m6.933s
user  0m6.404s
sys 0m0.028s
"""


print solve2(large)
"""
real  0m0.053s
user  0m0.040s
sys 0m0.012s