You are given an integer array prices where prices[i] is the price of NeetCoin on the ith day.
You may choose a single day to buy one NeetCoin and choose a different day in the future to sell it.
Return the maximum profit you can achieve. You may choose to not make any transactions, in which case the profit would be 0.
Example 1:
Input: prices = [10,1,5,6,7,1]
Output: 6 Explanation: Buy prices[1] and sell prices[4], profit = 7 - 1 = 6.
Example 2:
Input: prices = [10,8,7,5,2]
Output: 0 Explanation: No profitable transactions can be made, thus the max profit is 0.
Solution¶
- Use two pointers - one for buying (left) and one for selling (right)
- Only sell after buying (meaning we should scan future prices for selling) ie. left<right always
- Keeps track of the minimum price seen so far (potential buy point)
- For each day, calculates profit if we sell at current price
- Updates minimum price if we find a lower price
- Returns the maximum profit found
In [18]:
def maxProfit(prices):
left = 0 # buy
maxProfit = 0
for right in range(len(prices)): # sell
profit = prices[right] - prices[left]
if prices[right] < prices[left]:
left = right
maxProfit = max(maxProfit, profit)
return maxProfit
In [19]:
maxProfit([7,1,5,3,6,4])
Out[19]:
5
In [ ]: