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 1:
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.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
-
1 <= prices.length <= 105 -
0 <= prices[i] <= 104
SOLUTION:
# class Solution:
# def maxProfit(self, prices: List[int]) -> int:
# valIndex = {}
# maxProfit = 0
# for i, price in enumerate(prices):
# if price not in valIndex:
# valIndex[price] = [i, i]
# else:
# valIndex[price][1] = i
# newprices = sorted(valIndex.keys())
# n = len(newprices)
# for j in range(n - 1, -1, -1):
# end = newprices[j]
# if end - newprices[0] <= maxProfit:
# break
# for i in range(j):
# curr = end - newprices[i]
# if curr <= maxProfit:
# break
# if valIndex[end][1] > valIndex[newprices[i]][0]:
# maxProfit = max(maxProfit, curr)
# return maxProfit
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
minSoFar = prices[0]
maxDiffSoFar = 0
for i in range(1, n):
minSoFar = min(minSoFar, prices[i])
maxDiffSoFar = max(maxDiffSoFar, prices[i] - minSoFar)
return maxDiffSoFar
Top comments (0)