{"id":204,"date":"2020-07-06T00:12:21","date_gmt":"2020-07-06T00:12:21","guid":{"rendered":"http:\/\/96.126.106.214\/?p=204"},"modified":"2023-11-26T01:01:48","modified_gmt":"2023-11-26T01:01:48","slug":"buying-and-selling-stocks-with-maximum-profit","status":"publish","type":"post","link":"https:\/\/codingismycraft.blog\/index.php\/2020\/07\/06\/buying-and-selling-stocks-with-maximum-profit\/","title":{"rendered":"Buying and Selling stocks with maximum profit"},"content":{"rendered":"

Summary<\/h2>\n

This posting continues the discussion about algorithmic thinking solving a well know problem that is known as\u00a0 Best Time to Buy and Sell Stock<\/strong> with maximum profit.<\/p>\n

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.<\/p>\n

To gain the maximum value you should allocate enough time to try to solve it in an efficient way before you read the solution.<\/p>\n

The problem<\/h2>\n

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.<\/p>\n

For example assuming the following list of prices:<\/p>\n

[7, 3, 13, 13, 6, 19, 10, 8, 15, 18]<\/p>\n

the maximum profit that can be made is 26 <\/strong>which is made as follows:<\/p>\n

Buy at 3 – Sell at 19,\u00a0 Buy at 8 – Sell at 18<\/p>\n

as can be seen in this picture:<\/p>\n

\"bss-1\"<\/p>\n

Initial thoughts<\/h2>\n

From the first glance, the problem looks simple; as we will see shortly it is not!<\/p>\n

Thinking about the problem we can see that there exist three “types” of solutions:<\/p>\n

    \n
  • No pair of Buy – Sell that shows profit.<\/li>\n
  • One pair of Buy – Sell that shows the maximum profit.<\/li>\n
  • Two pairs of Buy – Sell that shows the maximum profit.<\/li>\n<\/ul>\n

    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:<\/p>\n

    \r\nimport itertools\r\n\r\ndef get_max_profit(prices):\r\n    all_indexes = list(range(len(prices)))\r\n\r\n    max_profit = 0\r\n    for i1, i2 in itertools.combinations(all_indexes, 2):\r\n\r\n        profit = prices[i2] - prices[i1]\r\n\r\n        if profit > max_profit:\r\n            max_profit = profit\r\n\r\n    for i1, i2, i3, i4 in itertools.combinations(all_indexes, 4):\r\n\r\n        profit = prices[i2] - prices[i1] + prices[i4] - prices[i3]\r\n        if profit > max_profit:\r\n            max_profit = profit\r\n\r\n    return max_profit\r\n\r\n<\/pre>\n
    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:<\/p>\n
    \r\nimport timeit\r\nimport functools\r\nimport random\r\n\r\ndef creating_dummy_prices(n):\r\n    """Creates a list or prices to use for stress testing.\r\n\r\n    :param int n: The length of the list to create.\r\n\r\n    :return: A list of prices.\r\n    :rtype: list.\r\n    """\r\n    return [random.randint(0, 20) for _ in range(n)]\r\n\r\nfor n in [10, 20, 100, 150, 200]:\r\n    data = creating_dummy_prices(n)\r\n    f = functools.partial(get_max_profit, data)\r\n    print(f'Number of prices: {n}', ' Duration in seconds', timeit.timeit(f, number=1))\r\n\r\n<\/pre>\n
    The code above produces the following output:<\/p>\n
    \"bss-3\"<\/p>\n
    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.<\/p>\n
    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:<\/p>\n
    \"bss-4\"<\/p>\n
    which translates to a quadratic time complexity:<\/p>\n
    \"bss-5\"<\/p>\n
    It is clear that we need to a smarter solution that will allow us to solve it in a more efficient way.<\/p>\n
    A better performing “brutal solution”<\/h2>\n
    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\u00a0 will be the desired value.<\/p>\n
    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.<\/p>\n
    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:<\/p>\n
    \r\nimport timeit\r\nimport functools\r\nimport random\r\n\r\n\r\ndef creating_dummy_prices(n):\r\n    """Creates a list or prices to use for stress testing.\r\n\r\n    :param int n: The length of the list to create.\r\n\r\n    :return: A list of prices.\r\n    :rtype: list.\r\n    """\r\n    return [random.randint(0, 20) for _ in range(n)]\r\n\r\n\r\ndef brutal_find_max_delta(a):\r\n    largest_so_far = None\r\n    lower_so_far = None\r\n    m = 0\r\n    for value in a:\r\n        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:\r\n            lower_so_far = value\r\n            largest_so_far = 0\r\n\r\n        m = max(m, largest_so_far - lower_so_far)\r\n    return m\r\n\r\n\r\ndef brutal_solution(b):\r\n    s = brutal_find_max_delta(b)\r\n    for i in range(2, len(b) - 1):\r\n        x1, x2 = b[0:i], b[i:]\r\n        s = max(s, brutal_find_max_delta(x1) + brutal_find_max_delta(x2))\r\n    return s\r\n\r\n\r\nfor n in [10, 20, 100, 150, 200]:\r\n    data = creating_dummy_prices(n)\r\n    f = functools.partial(brutal_solution, data)\r\n    print(f'Number of prices: {n}', ' Duration in seconds',\r\n          timeit.timeit(f, number=1))\r\n\r\n<\/pre>\n
    Which gives us the following output:<\/p>\n
    \"bss-6\"<\/p>\n
    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.<\/p>\n
    If we increase the size of the curve and run the following code:<\/p>\n
    \r\nfor n in [1000, 2000, 3000, 5000]:\r\n    data = creating_dummy_prices(n)\r\n    f = functools.partial(brutal_solution, data)\r\n    print(f'Number of prices: {n}', ' Duration in seconds',\r\n          timeit.timeit(f, number=1))\r\n<\/pre>\n
    we are getting the following timings:<\/p>\n
    \"bss-7\"<\/p>\n
    Although much faster than before, the function slows down quickly as the size of the curve grows.<\/p>\n
    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:<\/p>\n
      \n
    • Each data point in the curve divides it to a left – right section<\/li>\n
    • We can calculate the maximum profit by iterating through all the points and compare their left – right totals<\/li>\n
    • We need to calculate the maximum profit for each subsection<\/li>\n<\/ul>\n
       <\/p>\n
      The algorithm to calculate the maximum profit for a subsection is interesting so lets take a closer look onto it..<\/p>\n
      Maximum profit for sequence of prices<\/h2>\n
      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.<\/p>\n
      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) :<\/p>\n
      \"bss-8\"<\/p>\n
      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.<\/p>\n
      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.<\/p>\n
      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:<\/p>\n
      \r\ndef brutal_find_max_delta(a):\r\n    largest_so_far = None\r\n    lower_so_far = None\r\n    m = 0\r\n    for value in a:\r\n        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:\r\n            lower_so_far = value\r\n            largest_so_far = 0\r\n\r\n        m = max(m, largest_so_far - lower_so_far)\r\n    return m\r\n <\/pre>\n
      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).<\/p>\n
      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).<\/p>\n
      Based on this the total complexity of the brutal solution will be quadratic:<\/p>\n
      \"bss-9\"<\/p>\n
      So, although this approach is an improvement when compare to the previous solution, it is still very slow and needs to be improved further.<\/p>\n
      Tip: Before you continue be sure that you understand the implementation of brutal_find_max_delta.<\/p>\n
      Precalculating maximum profits<\/h2>\n
      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.<\/p>\n
      Doing so appears to be quite easy changing the brutal_find_max_delta to keep track of the maximums per point:<\/p>\n
      \r\ndef left_side_max_deltas(prices):\r\n    """Returns a list whose each element has the max delta from left side.\r\n\r\n    :param list prices: The list of prices.\r\n\r\n    :return: The list with the max delta from left.\r\n    :rtype: list.\r\n    """\r\n    deltas = [0] * len(prices)\r\n    largest_so_far = None\r\n    lower_so_far = None\r\n    m = 0\r\n    for index, value in enumerate(prices):\r\n        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:\r\n            lower_so_far = value\r\n            largest_so_far = 0\r\n\r\n        m = max(m, largest_so_far - lower_so_far)\r\n        deltas[index] = m\r\n\r\n    return deltas\r\n\r\n<\/pre>\n
      Calling this function using the above testing data:<\/p>\n
      \r\nprint(left_side_max_deltas([8, 12, 1, 9, 6, 11]))\r\n<\/pre>\n
      We are getting the following output:<\/p>\n
      [0, 4, 4, 8, 8, 10]<\/p>\n
      as can be seen in this graph:<\/p>\n
      \"bss-10\"<\/p>\n
      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:<\/p>\n
      \r\ndef right_side_max_deltas(prices):\r\n    """Returns a list whose each element has the max delta from right side.\r\n\r\n    :param list prices: The list of prices.\r\n\r\n    :return: The list with the max delta from right.\r\n    :rtype: list.\r\n    """\r\n    deltas = [0] * len(prices)\r\n    index = len(prices) - 1\r\n\r\n    largest_so_far = None\r\n    lower_so_far = None\r\n    m = 0\r\n\r\n    while index >= 0:\r\n        value = prices[index]\r\n\r\n        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:\r\n            lower_so_far = value\r\n\r\n        m = max(m, largest_so_far - lower_so_far)\r\n        deltas[index] = m\r\n\r\n        index -= 1\r\n\r\n    return deltas\r\n\r\n<\/pre>\n
      Running the new functions with the same curve as before:<\/p>\n
      \r\nprint(right_side_max_deltas([8, 12, 1, 9, 6, 11]))\r\n<\/pre>\n
      returns the following list:<\/p>\n
      [10, 10, 10, 5, 5, 0]<\/p>\n
      where each data point represents the maximum area that can be found on the right of it as can be seen in this graph:<\/p>\n
      \"bss-11\"<\/p>\n
      The efficient solution<\/h2>\n
      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:<\/p>\n
      \r\n\r\ndef get_max_profit(prices):\r\n    m = 0\r\n    index = 0\r\n    left = left_side_max_deltas(prices)\r\n    right = right_side_max_deltas(prices)\r\n    while index < len(prices):\r\n        m = max(m, left[index] + right[index])\r\n        index += 1\r\n    return m\r\n\r\nassert get_max_profit([7, 3, 13, 13, 6, 19, 10, 8, 15, 18]) == 26\r\n\r\n<\/pre>\n
      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).<\/p>\n
      Stress testing our new function gives the following results:<\/p>\n
      \r\nfor n in [10, 20, 100, 150, 200, 1000, 10000, 100000]:\r\n    data = creating_dummy_prices(n)\r\n    f = functools.partial(get_max_profit, data)\r\n    print(f'Number of prices: {n}', ' Duration in seconds',\r\n          timeit.timeit(f, number=1))\r\n<\/pre>\n
      \"bss-12\"<\/p>\n
      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.<\/p>\n
      Conclusion<\/h2>\n
      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.<\/p>\n","protected":false},"excerpt":{"rendered":"
      Summary This posting continues the discussion about algorithmic thinking solving a well know problem that is known as\u00a0 Best Time to Buy and Sell Stock…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"footnotes":""},"categories":[6],"tags":[],"class_list":["post-204","post","type-post","status-publish","format-standard","hentry","category-programming"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack-related-posts":[{"id":211,"url":"https:\/\/codingismycraft.blog\/index.php\/2020\/07\/01\/thinking-about-algorithmic-problems\/","url_meta":{"origin":204,"position":0},"title":"Thinking about Algorithmic problems","author":"john","date":"July 1, 2020","format":false,"excerpt":"In this posting we will discuss algorithmic thinking and try to propose a way of thinking that might become helpful when trying to solve a problem that does not have an obvious solution and some level of improvisation is required. Based on my experience the three most important qualities of\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":187,"url":"https:\/\/codingismycraft.blog\/index.php\/2020\/07\/03\/thinking-about-algorithmic-problems-ii\/","url_meta":{"origin":204,"position":1},"title":"Thinking about Algorithmic problems II","author":"john","date":"July 3, 2020","format":false,"excerpt":"Solving a programming problem that requires a custom algorithm can be broken in several steps which can be summarized in the creation of testing data, the implementation of a brutal force solution and the deeper study of the particular case which might reveal a smart trick to achieve an efficient\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":348,"url":"https:\/\/codingismycraft.blog\/index.php\/2025\/03\/19\/stop-chasing-technology-how-to-build-ai-that-solves-genuine-problems\/","url_meta":{"origin":204,"position":2},"title":"Stop Chasing Technology: Finding the user\u2019s problem is the real problem!","author":"john","date":"March 19, 2025","format":false,"excerpt":"There\u2019s a common critique in the AI community: too often, AI solutions emerge from asking, \u201cWhat can we do?\u201d rather than, \u201cWhat problem do we need to solve?\u201d Developers frequently jump on the latest algorithm or innovative model and then search for a suitable use case. This approach tends to\u2026","rel":"","context":"In "AI"","block_context":{"text":"AI","link":"https:\/\/codingismycraft.blog\/index.php\/category\/ai\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":40,"url":"https:\/\/codingismycraft.blog\/index.php\/2013\/03\/11\/abstractions-and-specializations\/","url_meta":{"origin":204,"position":3},"title":"Abstractions and Specializations","author":"john","date":"March 11, 2013","format":false,"excerpt":"Sometimes when developing a solution I stop my coding for a several minutes visualizing my work as a battle between abstractions and specializations. The contrast of these opposites is a major characteristic of any program developed ever and the talent, experience and determination of the developer are stamping the final\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":223,"url":"https:\/\/codingismycraft.blog\/index.php\/2013\/05\/11\/sudoku-solver-in-python\/","url_meta":{"origin":204,"position":4},"title":"Sudoku Solver in Python","author":"john","date":"May 11, 2013","format":false,"excerpt":"A great way to learn a new language is to simulate a game using it. Implementing a solution for something that seems so simple as a black jack game or texas holdem usually presents enough of a challenge to at least get the feeling of the language. Sudoku seemed like\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":64,"url":"https:\/\/codingismycraft.blog\/index.php\/2015\/10\/07\/metrics-converted-to-goals-lose-their-focus\/","url_meta":{"origin":204,"position":5},"title":"Metrics converted to goals lose their focus","author":"john","date":"October 7, 2015","format":false,"excerpt":"One of the common discussions I have had with my colleagues over the last years was about the creation of metrics to express the productivity and the quality of an individual developer. At first glance, the idea of expressing the ability of a programmer, with a small set of easy\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts\/204","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/comments?post=204"}],"version-history":[{"count":4,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts\/204\/revisions"}],"predecessor-version":[{"id":208,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts\/204\/revisions\/208"}],"wp:attachment":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/media?parent=204"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/categories?post=204"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/tags?post=204"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}