## Summary

This posting continues the discussion about algorithmic thinking solving a well know problem that is known as ** Best Time to Buy and Sell Stock** with maximum profit.

The solution to this problem is hard and I do not believe that it makes a good interview question but it is still a good exercise that might take an intermediate developer a few hours to solve.

To gain the maximum value you should allocate enough time to try to solve it in an efficient way before you read the solution.

## The problem

We are given a list of integers representing stock prices; we must find the maximum profit that can be made assuming at most two no overlapping BUY – SELL transactions.

For example assuming the following list of prices:

[7, 3, 13, 13, 6, 19, 10, 8, 15, 18]

the maximum profit that can be made is **26 **which is made as follows:

Buy at 3 – Sell at 19, Buy at 8 – Sell at 18

as can be seen in this picture:

## Initial thoughts

From the first glance, the problem looks simple; as we will see shortly it is not!

Thinking about the problem we can see that there exist three “types” of solutions:

- No pair of Buy – Sell that shows profit.
- One pair of Buy – Sell that shows the maximum profit.
- Two pairs of Buy – Sell that shows the maximum profit.

It is trivial to convert this approach to a function that creates all the pairs by 2 and 4 points and return the maximum profit:

import itertools def get_max_profit(prices): all_indexes = list(range(len(prices))) max_profit = 0 for i1, i2 in itertools.combinations(all_indexes, 2): profit = prices[i2] - prices[i1] if profit > max_profit: max_profit = profit for i1, i2, i3, i4 in itertools.combinations(all_indexes, 4): profit = prices[i2] - prices[i1] + prices[i4] - prices[i3] if profit > max_profit: max_profit = profit return max_profit

To make performance testing easier lets create a function to return a random price sequence and run the get_max_profit function for different sizes of input:

import timeit import functools import random def creating_dummy_prices(n): """Creates a list or prices to use for stress testing. :param int n: The length of the list to create. :return: A list of prices. :rtype: list. """ return [random.randint(0, 20) for _ in range(n)] for n in [10, 20, 100, 150, 200]: data = creating_dummy_prices(n) f = functools.partial(get_max_profit, data) print(f'Number of prices: {n}', ' Duration in seconds', timeit.timeit(f, number=1))

The code above produces the following output:

Note that a sequence of 20 points requires a few milliseconds but as we ramp up to 200 we are quickly reaching more than 13 seconds.

This happens because our solution is extremely slow; note that we are calculating all the possible pairs for 2 and 4 points taken from prices meaning that the number of the required profit calculations are given by the following formula:

which translates to a quadratic time complexity:

It is clear that we need to a smarter solution that will allow us to solve it in a more efficient way.

## A better performing “brutal solution”

As we think the problem deeper, we realize that for each data point in the prices curve we have a left – right maximum profit transaction meaning that if we iterate though all the points and store all the totals (counting only positive values) their maximum will be the desired value.

In this case the complexity of our solution will be proportional to the size of the array multiplied by the cost of finding the larger transaction in the left – right sides of the curve.

To try this approach we need to create a function that will receive a subsection of prices and return the maximum possible profit for it what is important though is that we want to avoid the creation of all possible pairs as we have done before and reduce the finding of the largest profit transaction to a single pass per subsection. After a little thinking we end up with the following solution:

import timeit import functools import random def creating_dummy_prices(n): """Creates a list or prices to use for stress testing. :param int n: The length of the list to create. :return: A list of prices. :rtype: list. """ return [random.randint(0, 20) for _ in range(n)] def brutal_find_max_delta(a): largest_so_far = None lower_so_far = None m = 0 for value in a: if largest_so_far is None or largest_so_far < value: largest_so_far = value if lower_so_far is None or lower_so_far > value: lower_so_far = value largest_so_far = 0 m = max(m, largest_so_far - lower_so_far) return m def brutal_solution(b): s = brutal_find_max_delta(b) for i in range(2, len(b) - 1): x1, x2 = b[0:i], b[i:] s = max(s, brutal_find_max_delta(x1) + brutal_find_max_delta(x2)) return s for n in [10, 20, 100, 150, 200]: data = creating_dummy_prices(n) f = functools.partial(brutal_solution, data) print(f'Number of prices: {n}', ' Duration in seconds', timeit.timeit(f, number=1))

Which gives us the following output:

Note that calculating the maximum profit now takes 0.16 which compared to the 13.29 that we have gotten before looks like a great improvement but we still have more work to do.

If we increase the size of the curve and run the following code:

for n in [1000, 2000, 3000, 5000]: data = creating_dummy_prices(n) f = functools.partial(brutal_solution, data) print(f'Number of prices: {n}', ' Duration in seconds', timeit.timeit(f, number=1))

we are getting the following timings:

Although much faster than before, the function slows down quickly as the size of the curve grows.

Before we move forward and try to improve our solution it will be helpful to understand our current solution which is based on two basic concepts:

- Each data point in the curve divides it to a left – right section
- We can calculate the maximum profit by iterating through all the points and compare their left – right totals
- We need to calculate the maximum profit for each subsection

The algorithm to calculate the maximum profit for a subsection is interesting so lets take a closer look onto it..

## Maximum profit for sequence of prices

Calculating the transaction with the maximum profit for a sub-sequence is at the heart of our solution and we need to digest it well in order to understand the solution to our problem.

Given the sequence of prices [8, 12, 1, 9, 6, 11] it is easy to conclude that the maximum profit that can be made is 10 (buy on the third point and sell in the tenth) :

To find out this profit we will need to iterate through the whole curve and at each point “remember” the lowest and highest prices we have seen so far. More than this we need to be sure that the lowest price occurs before the highest; this is what makes this algorithm a bit tricky.

As we move forward (to the right) if we discover a new lowest price we reinitialize our stored lower value to the new one and also set the maximum value to zero otherwise if we have reached a new larger value we are replacing the larger value so far with it.

At this point it is simple to calculate the larger profit for any iteration point if we compare the current profit with the previous, this is exactly what this code is doing:

def brutal_find_max_delta(a): largest_so_far = None lower_so_far = None m = 0 for value in a: if largest_so_far is None or largest_so_far < value: largest_so_far = value if lower_so_far is None or lower_so_far > value: lower_so_far = value largest_so_far = 0 m = max(m, largest_so_far - lower_so_far) return m

Since we are iterating through all the prices passed to the function its complexity is O(m) (m is the length of the passed in array).

As said before to calculate the maximum possible profit for zero, one or two transactions we need to iterate through the whole sequence of prices (whose length is n) and for each point call the brutal_find_max_delta function for the left and right side. Note the for each point the complexity will be: O(m) + O(n-m) or O(n).

Based on this the total complexity of the brutal solution will be quadratic:

So, although this approach is an improvement when compare to the previous solution, it is still very slow and needs to be improved further.

Tip: Before you continue be sure that you understand the implementation of brutal_find_max_delta.

## Precalculating maximum profits

In our solution about we note that what is really “expensive” is the calculation of the left – right maximums; this makes us to think if we can simplify their calculations by re-using some of the already calculated data. Our approach will be to create a new list having the same length as the passed in list of prices where each point will have the left-wise maximum profit.

Doing so appears to be quite easy changing the brutal_find_max_delta to keep track of the maximums per point:

def left_side_max_deltas(prices): """Returns a list whose each element has the max delta from left side. :param list prices: The list of prices. :return: The list with the max delta from left. :rtype: list. """ deltas = [0] * len(prices) largest_so_far = None lower_so_far = None m = 0 for index, value in enumerate(prices): if largest_so_far is None or largest_so_far < value: largest_so_far = value if lower_so_far is None or lower_so_far > value: lower_so_far = value largest_so_far = 0 m = max(m, largest_so_far - lower_so_far) deltas[index] = m return deltas

Calling this function using the above testing data:

print(left_side_max_deltas([8, 12, 1, 9, 6, 11]))

We are getting the following output:

[0, 4, 4, 8, 8, 10]

as can be seen in this graph:

With a simple modification of the left_side_max_deltas we can write a similar function to calculate the maximums from the right side of a point:

def right_side_max_deltas(prices): """Returns a list whose each element has the max delta from right side. :param list prices: The list of prices. :return: The list with the max delta from right. :rtype: list. """ deltas = [0] * len(prices) index = len(prices) - 1 largest_so_far = None lower_so_far = None m = 0 while index >= 0: value = prices[index] if largest_so_far is None or largest_so_far < value: largest_so_far = value lower_so_far = value if lower_so_far is None or lower_so_far > value: lower_so_far = value m = max(m, largest_so_far - lower_so_far) deltas[index] = m index -= 1 return deltas

Running the new functions with the same curve as before:

print(right_side_max_deltas([8, 12, 1, 9, 6, 11]))

returns the following list:

[10, 10, 10, 5, 5, 0]

where each data point represents the maximum area that can be found on the right of it as can be seen in this graph:

## The efficient solution

Now that we have the left – right maximum profit curve creation functions ready we can write a function to allow us to solve the problem:

def get_max_profit(prices): m = 0 index = 0 left = left_side_max_deltas(prices) right = right_side_max_deltas(prices) while index < len(prices): m = max(m, left[index] + right[index]) index += 1 return m assert get_max_profit([7, 3, 13, 13, 6, 19, 10, 8, 15, 18]) == 26

The time complexity of our solution is O(n) and since we are keeping the pre-calculated maximums in memory our memory complexity is also O(n).

Stress testing our new function gives the following results:

for n in [10, 20, 100, 150, 200, 1000, 10000, 100000]: data = creating_dummy_prices(n) f = functools.partial(get_max_profit, data) print(f'Number of prices: {n}', ' Duration in seconds', timeit.timeit(f, number=1))

Notice how dramatically faster the new solution is;a price curve of 100,000 data points now takes less than a tenth of a second to be calculated meaning that we have reached an effective and acceptable solution.

## Conclusion

To solve our problem we initially created a very simple solution which was very slow, thinking a little deeper we were able to improve its performance to be faster and then we discovered a trick that allowed us to come up with an efficient algorithm for our problem; the same process is applicable to most of the problems that require a special algorithm.

> Given the sequence of prices [8, 12, 1, 9, 6, 11] it is easy to conclude that the maximum profit that can be made is 10 (buy on the third point and sell in the [sixth])

I think you’re mis-reading the problem. Maximum profit for at most 2 non-overlapping buy/sell transactions. For the series you gave, that would be Buy at 1, Sell at 9, Buy at 6, Sell at 11: yielding a profit of 13. Not 10 as you stated.

Thanks for the comment..

Will try to explain it better:

Note that the calculation you are referring to is applied after we have split the curve to left are right and we try to find the max profit for each side to add them up. To make it cleaner assume that the curve is as follows: [2, 12, 32, 8, 12, 1, 9, 6, 11]

The max profit for index = 2 will be given from the max_profit([2, 12, 32] + max_profit([8, 12, 1, 9, 6, 11]) (meaning that each max profit returns the single most profitable transaction for each sequence).. The two – side max profit of [8, 12, 1, 9, 6, 11] will be given be the left – fight profits at index 3 consisting of the pair: [8, 12, 1, 9] [ 6, 11] or 8 + 5 = 13

I see now, I was confusing your comments for one step of the algorithm as being about the whole. This is an interesting post. I liked seeing the step-wise development of a more efficient solution.