Instructions
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example
Input: prices = [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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Approach
To make a profit, you buy low and sell high. Therefore, we are looking for days where the price is low and when its high, we determine the difference and get maximum profit.
We can get a list of all the differences between prices on adjacent days using list comprehension then determine the max profit by finding the max between the prices.
def maxProfit(prices):
diff_prices = [prices[i+1] - prices[i] for i in range(len(prices) - 1)]
max_profit = 0
current_profit = 0
for profit in diff_prices:
current_profit += profit
if current_profit < profit:
current_profit = profit
max_profit = max(max_profit, current_profit)
return max_profit
Approach 2
We will use two pointers, left and right, where the right is at left+1 to get the differences and update the pointers. Whenever we encounter a new minimum we will automatically update the left pointer to that value.
Python Implementation.
def maxProfit(self, prices: List[int]) -> int:
maximum_profit = 0
left = 0
right = left+1
while right < len(prices):
if prices[right] > prices[left]:
profit = prices[right]- prices[left]
maximum_profit = max(profit,maximum_profit)
right +=1
else:
left=right
right +=1
return maximum_profit
Top comments (0)