Leetcode: Best time to buy and sell stock
The task is to find out of a series of stock prices the best time to buy and sell the stock. Only one stock can be owned at the time and it can be sold and bought at the same time.
The Python solution looks like this. It’s not entirely optimal because technically we could sell stock at every transaction, which simplifies the code as shown below.
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
buy = -1
for i in range(len(prices) - 1):
if buy == -1:
if prices[i] < prices[i + 1]:
buy = prices[i]
else:
if prices[i] > prices[i+1]:
profit += (prices[i] - buy)
buy = -1
if buy > -1:
profit += prices[-1] - buy
return profit
if __name__ == '__main__':
r = Solution().maxProfit
print(r([7,1,5,3,6,4]), 7)
print(r([1,2,3,4,5]), 4)
print(r([7,6,4,3,1]), 0)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
buy = -1
for i in range(len(prices) - 1):
# See if I can sell
if buy > -1:
profit += (prices[i] - buy)
buy = -1
# See if I should buy again
if prices[i] < prices[i + 1]:
buy = prices[i]
if buy > -1:
profit += prices[-1] - buy
return profit
func maxProfit(prices []int) int {
profit := 0
ownStock := false
lastPrice := prices[0]
boughtAt := 0
for i := 1; i < len(prices); i++ {
currPrice := prices[i]
if ownStock {
// Check if should sell
if currPrice < lastPrice {
profit += lastPrice - boughtAt
ownStock = false
}
} else {
// Check if should buy
if currPrice > lastPrice {
boughtAt = lastPrice
ownStock = true
}
}
lastPrice = currPrice
}
// Sell at the end
if ownStock {
profit += prices[len(prices)-1] - boughtAt
}
return profit
}