An interesting concept in Finance and Computer Science is if we have some historical data about the price of a security and we want to see the maximum profit we can make. (Assumption: we can only carry out one buy and one sell action)

Let’s assume that time is represented by natural numbers as opposed to timestamps. With this, we can represent the prices as an array and the index of the array representing the timestamp value (the lower values being earlier prices).

So given the array: [4.5, 6.0, 4.2, 4.4, 7.0, 3.2] the maximum profit we can make is 7.0 – 4.2 = 2.8

The solution may seem tricky as there are local sub-array problems that need to be solved, for example if we have gone through the first four elements of the array above, we can’t really say anything about the profit until we see more elements of the array.

The solution that I came up with had two variables and keeps track of the current maximum profit by continuous calculation and the minimum price value. This concept surprisingly leads to an elegant solution.

My solution (implemented in Python) is below, it’s got a complexity of O(n) – there has to be at least one element in the array.

[sourcecode language=”python”]

def max_profit(array):
profit = 0
min = array[0]
for i in array:
if i < min:
min = i
if (i – min > profit):
profit = (i – min)
return profit

[/sourcecode]