This article presents an algorithmic problem with practical value for stock market analysis. For instance, suppose you are trading the cryptocurrency Ethereum. How much profit in dollars can you make by buying low and selling high based on historical data?
Table of Contents
Maximum Profit Basic Algorithm
The max profit algorithm calculates the maximum profit you’d obtain by buying low and selling high:
# Profit of a single
# buying low and selling high
def maximumProfit(A):
m = 0
for i in range(0, len(A)):
for j in range (i + 1, len(A)):
m = max(m, A[j] - A[i])
return m
# Ethereum daily prices in Dec 2017 ($)
prices = [455,460,465,451,414,415,441]
print(maximumProfit(prices))
# 27
Exercise: Take a guess–what is the output of this code snippet?
Maximum Profit Algorithm Description
The function maximumProfit takes an input sequence A, e.g. a week of Ethereum prices in December 2017. It returns the largest profit of buying low and selling high.
The algorithm works as follows:
It iterates over all sequence indices i, i.e., the buying points, and over all sequence indices j>i, i.e., the selling points. For each buying/selling pair (i,j), it calculates the profit as the difference between the prices at the selling and the buying points, i.e., A[j]-A[i]. The variable profit maintains the largest possible profit: $27 on $414 invested capital.
This implementation has quadratic runtime as you have to check O(n*n) different combinations of buying and selling points. You’ll learn about a linear-runtime solution later.
Alternative Maximum Profit Algorithm with Slicing
Here’s a slight variant of the above algorithm:
# Profit of a single
# buying low and selling high
def maximumProfit(A):
m = 0
for i in range(0, len(A)-1):
buy, sell = A[i], max(A[i+1:])
m = max(m, sell-buy)
return m
# Ethereum daily prices in Dec 2017 ($)
prices = [455,460,465,451,414,415,441]
print(maximumProfit(prices))
# 27
It’s a bit more readable and uses slicing instead of the second nested for loop.
Alternative Maximum Profit Algorithm – Linear Runtime
the following algorithm has linear runtime and is much more efficient for a single-sell max-profit algorithm:
def maximumProfit(A):
buy, m = 0, 0
for i in range(len(A)):
buy = min(buy, A[i])
profit = A[i] - buy
m = max(m, profit)
return m
# Ethereum daily prices in Dec 2017 ($)
prices = [455,460,465,451,414,415,441]
print(maximumProfit(prices))
# 27
Maximum Profit Python Puzzle
Before I show you the solution to the max profit example in the code—can you solve this code puzzle on our interactive Python puzzle app?
Click to solve the exercise and test your Python skills!
Are you a master coder? Test your skills now!
Related Video
Solution
The maximum profit in the above algorithm of buying low and selling high for the list of prices [455,460,465,451,414,415,441] is:
27
You buy at $414 and sell at $441 which leads to a profit of $441-$414=$27.
Would you enjoy becoming the best Python coders in your environment? Here’s a decision you won’t regret: join my Python email academy. It’s the most comprehensive Python email academy in the world!
