#This example is to find maximum viable stock profit using 1 transaction
import time
import random

#Compare all of available transaction, and calculate maximum profit
def max_profit_slow(prices):
	n = len(prices)
	max_profit = 0

	for i in range(0, n-1):
		for j in range(i+1,n):
			profit = prices[j] - prices[i]
			if profit > max_profit:
				max_profit = profit
	return max_profit

# Faster algorithm: remember max_profit and minimum price at the time
## There is time-dependency in transaction
## If the price at time i is below initial price, only compare the maximum profit in time priods before and after time i
def max_profit_fast(prices):
	n = len(prices)
	max_profit = 0
	min_price = prices[0]

	for i in range(1, n):
		profit = prices[i] - min_price
		if profit > max_profit:
			max_profit = profit
		if prices[i] < min_price:
			min_price = prices[i]

	return max_profit



#Performacne Analysis between two algorithms
def test(n):
	a = []
	for i in range(0,n):
		a.append(random.randint(5000,20000))

	start = time.time()
	mps = max_profit_slow(a)
	end = time.time()
	time_slow = end-start

	start = time.time()
	mpf = max_profit_fast(a)
	end = time.time()

	time_fast = end - start
	print n, mps, mpf

	m = 0
	if time_fast > 0:
		m = time_slow/time_fast

	print n, time_slow, time_fast, m

test(100)
test(10000)

