The Maximum Profit Algorithm in Python

by

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?

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 from 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.

💡 Algorithmic Complexity: This implementation has quadratic runtime complexity 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.

Maximum Profit Algorithm with Linear Runtime in Python

The following algorithm has linear runtime complexity 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

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.

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

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!

Leave a Comment