Maximum Profit Problem

Felicia Amy
Nov 8 · 3 min read

I got this question not long time ago, I believe this is a very common question that people often got during interviews. The question goes something like this:

Photo by Pixabay from Pexels

Given a list of stock price for certain number of days, you can decide when to buy and sell a stock that can give you the most profit. You can only buy 1 stock a day (for simplicity) and you can sell as many as you want at any days. Return the maximum profit you can generate from this.

Examples:
Stock Prices: [1, 2, 50]
Result : 97
Explanation: we buy 1 stock on 1st and 2nd day and sell on the 3rd day. This way we will spend 3 and get 100 by selling 2 stocks on the last day, which gives us a profit of 97.

Stock Prices: [1, 5, 2, 3, 5]
Result: 9
Explanation: we can do this in 2 ways: First, we buy a stock on the 1st day and then sell it on the 2nd day, continue with buying stocks on the 3rd and 4th days then sell them on the last day. Second way is to buy the stocks from day 1 to 4 and sell all of them on the last day.

Stock Prices: [10, 9, 1]
Result: 0


Looking at this problem, my first thought was dynamic programming since for every step we will be having 3 options: sell, buy, skip. However this will be an expensive solution: O(n²).

I figured since we can only buy at most 1 stock each day, this could be solved with a simpler and cheaper solution. This is what I noticed, if we have a set of price with an increasing price of stocks, it is always the most profitable to buy stocks everyday and sell all on the last day. For example, if we have [1, 2, 3, 4, 5], we can buy 1 stock everyday from day 1 until day 4 which cost us 10, and then sell it on the day 5 which gives us 5 * 4 = 20, so we will get 10 as the maximum profit.

Given the observation above, we can apply this in other patterns too. Taking this as example: [1, 5, 2, 3, 5], we can split this into 2 lists: [1, 5] and [2, 3, 5] and maximum profit will be the total of maximum profit for each lists which in this case 4 + 5 = 10. So, the key here to keep finding a list of increasing numbers.

This is the simplest code that we can write to solve this:

def findMaxProfit(prices):
profit, maxSoFar = 0, 0
for i in range(len(prices) - 1, -1, -1):
if prices[i] >= maxSoFar:
maxSoFar = prices[i]
profit += maxSoFar - prices[i]
return profit

As you can see in the code, we will subtract the maxSoFar with itself (it’s equal with skipping it, kinda…) and then add the difference of its precedents. If we have a list of prices: [1, 3, 8, 8, 7, 6, 7], we will not count non-increasing numbers (8, 8, 7 and 7). In above example, from back to front, the code goes something like this:

profit = 0
maxSoFar = 0
maxSoFar = 7
profit = 0
maxSoFar = 7
profit = 7 - 6 = 1
maxSoFar = 7
profit = 1
maxSoFar = 8
profit = 1
maxSoFar = 8
profit = 1
maxSoFar = 8
profit = 1 + (8 - 3) = 6
maxSoFar = 8
profit = 6 + (8 - 1) = 13

Time complexity: O(n)
Space complexity: O(1)
* No additional space needed


Next challenge:
Now to complicate the situation, you are given an integer K which is the number of transaction you can make. Transaction here meaning buying and selling. If K = 2, it means that we can only buy 1 stock and sell 1 stock. Good luck! :)

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade