Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
The description was taken from https://leetcode.com/problems/best-time-to-buy-and-sell-stock/.
#O(N) Time, O(1) Spaceclass Solution: def maxProfit(self, prices: List[int]) -> int: max_profit, min_price = 0, float('inf') for price in prices: min_price = min(min_price, price) max_profit = max(max_profit, price - min_price) return max_profitThis problem can be solved by keeping a couple of counters.
We will want to keep a minimum price and a maximum profit counter that we will update as we traverse the array.
The minimum price of a stock will determine the maximum profit we could gain from a sale of that stock once it increases.
The reason we want to update these values as we go and not just calculate at the end is that we may have an incorrect timeline for how the sale happened. If we had an array where the minimum price was one and the maximum was seven, if we were to just calculate the maximum subtracted by the minimum, well that would work if the one had a lesser index than the seven because that would signify that we bought in at one and sold at seven. What if it was the other way around? We would have actually bought in at seven and sold at one, which is not stonks at all.
Instead of implementing a difficult algorithm where we would cache the indices of the values and calculate the maximum profit like that, we can just update the minimum price, and also the current price subtracted by the minimum within each iteration to derive the maximum profit possible for each day, then return the sale that gave us the most profit.
We will initialize our max profit to zero, as this would be the base case. We also will set our min price to infinity so we can overwrite it with any lower price within the bounds of our input array.
max_profit, min_price = 0, float('inf')
We will then traverse our prices and during each iteration, we set the minimum price to the lowest value between our saved minimum price and the current price.
for price in prices: min_price = min(min_price, price)
Within each iteration, we will consider selling at today's price, using the lowest buy-in date we have seen so far.
If our profit would be higher than we had previously considered, we will keep this sale as the maximum profit so far.
max_profit = max(max_profit, price - min_price)
Since we are calculating the maximum profit with the minimum price, we ensure that we can only calculate a viable profit after a minimum price has already been set. This validates that we are only selling stocks after we have bought.
We'll return the max profit once we've traversed the entire list.
return max_profit