Buying and Selling stocks with maximum profit

栏目: IT技术 · 发布时间: 3年前

内容简介:This posting continues the discussion about algorithmic thinking solving a well know problem that is known asThe 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 a
Buying and Selling stocks with maximum profit

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.

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:

Buying and Selling stocks with maximum profit

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):
        assert i1 < i2 profit = prices[i2] - prices[i1] if profit > max_profit:
            max_profit = profit

    for i1, i2, i3, i4 in itertools.combinations(all_indexes, 4):
        assert i1 < i2 < i3 < i4 profit = prices[i2] - prices[i1] + prices[i4] - prices[i3] if profit > max_profit:
            max_profit = profit

    return max_profit

assert get_max_profit([7, 3, 13, 13, 6, 19, 10, 8, 15, 18]) == 26

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:

Buying and Selling stocks with maximum profit

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:

Buying and Selling stocks with maximum profit

which translates to a quadratic time complexity:

Buying and Selling stocks with maximum profit

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:

Buying and Selling stocks with maximum profit

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:

Buying and Selling stocks with maximum profit

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) :

Buying and Selling stocks with maximum profit

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:

Buying and Selling stocks with maximum profit

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:

Buying and Selling stocks with maximum profit

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:

Buying and Selling stocks with maximum profit

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))

Buying and Selling stocks with maximum profit

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.


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法笔记

算法笔记

胡凡、曾磊 / 机械工业出版社 / 2016-7 / 65

这是一本零基础就能读懂的算法书籍,读者不需要因为自己没有语言基础而畏惧。书籍的第2章便是一个C语言的入门教程,内容非常易懂,并且十分实用,阅读完这章就可以对本书需要的C语言基础有一个较好的掌握。 本书已经覆盖了大部分基础经典算法,不仅可以作为考研机试和PAT的学习教材,对其他的一些算法考试(例如CCF的CSP考试)或者考研初试的数据结构科目的学习和理解也很有帮助,甚至仅仅想学习经典算法的读者......一起来看看 《算法笔记》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码