-
Notifications
You must be signed in to change notification settings - Fork 0
/
best_buy_sell_stock.py
41 lines (32 loc) · 1.19 KB
/
best_buy_sell_stock.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
'''
Question: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
'''
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
'''
use sliding window to find the best buy and sell prices
TC: O(n)
SC: O(1)
'''
# init maxProfit as 0
maxProfit = 0
# assume buy and sell as first two prices (indexes)
buy, sell = 0, 1
# loop until sell doesn't reach the end of prices list
while sell < len(prices):
# if curr_price (or sell) is greater than buy price,
if prices[buy] < prices[sell]:
# calculate the profit
profit = prices[sell] - prices[buy]
# check if current profit `profit` is greater
# than all time profit `maxProfit`
maxProfit = max(maxProfit, profit)
# if curr_price (or sell) is less than buy price,
# assign buy to curr_price
else:
buy = sell
# keep incrementing sell price pointer in hope to
# find the best price to sell
sell += 1
return maxProfit