In this approach, we’re checking all possible values of . Hence, we call this the brute force approach.
We iterate over all possible pairs and , such that always starts from and moves forward. The index represents the day we buy the product. On the other hand, the index represents the day we sell the product.
Therefore, starts from and moves forward because we can’t sell a product if we haven’t bought it yet.
For each pair (, ), we check whether we can get a better profit from the already found profit. If so, we update the stored profit. Also, we store the day we decided to buy the product and the day we decided to sell it.
In the end, we return the stored answer and both indexes of the days to buy and sell the product in.
The complexity of the naive approach is , where is the number of days.
4. Dynamic Programming Approach
Let’s try to improve our naive approach.
4.1. General Idea
In the naive approach, we tried all possible pairs of days and . However, if we think deeply, we can see that when we decide to sell a product on the day , it’s always optimal to choose the smallest price in days to buy the product in before selling it.
So, in each step, we need to calculate the value , which stores the smallest value before, and including, the current index . Let’s use dynamic programming to calculate the values quickly.
Suppose we calculated the lowest price values before the index , and we need to calculate the value when we reached the index . The first solution would be to iterate over all the values in range and take the minimum value among them.
However, we can notice that the previous value of represents the range . Since the current range is , we can see that it differs only by the index from the previous range.
Thus, we can simply calculate the minimum value in range by taking the minimum between the previous value of and .
Let’s take the following example to explain the idea better:
First of all, we assign because we don’t have a previous range yet. After that, for each index we take the minimum between the previous value of and .
Now that we showed how to calculate the values, we can use it to improve the naive approach.
4.2. Implementation
Take a look at the implementation of the dynamic programming approach:
algorithm MaxSingleSellProfitDP(P, n):
// INPUT
// P = the prices array
// n = the size of the prices array
// OUTPUT
// The maximum single-sell profit, buy day, and sell day
indexOfLowest <- 0
Lowest <- P[0]
Answer <- 0
buyDay <- 0
sellDay <- 0
for j <- 1 to n:
if P[j] <= Lowest:
indexOfLowest <- j
Lowest <- P[j]
if Answer <= P[j] - Lowest:
Answer <- P[j] - Lowest
buyDay <- indexOfLowest
sellDay <- j
return Answer, buyDay, sellDay
Instead of calculating an entire array , we’ll just keep a variable named , that stores the minimum value so far.
In each step, we check if the current value is smaller than the lowest price so far. If so, we update the value of and . Note that we’ll store the index of the minimum value to be able to determine the day that we should buy the product in.
After that, we check whether the current selling day with the lowest buying day gives a better solution than the stored one. If so, we store the profit we get as the best one so far. Also, we’ll store the index as the buying day and index as the selling day.
Finally, we return the stored answer and both indexes of the buying and selling days.
The complexity of this approach is , where is the number of days.
5. Conclusion
In this tutorial, we explained the problem of finding the maximum single-sell profit from an array of prices. In the beginning, we presented the naive approach. Then, we showed how to improve it to obtain a dynamic programming solution.