問題地址：
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
解決方法：
#best-time-to-buy-and-sell-stock-i
from typing import *
class Solution:
def maxProfit(self, prices: List[int]) -> int:
maxProfit = 0
length = len(prices)
if not prices or length <= 1:
return maxProfit
minValue = float("inf")
maxValue = float("-inf")
result = 0
for i in range(length-1):
if prices[i] < minValue:
minValue = prices[i]
if prices[i+1] > prices[i]:
maxValue = prices[i+1]
result = max(result, maxValue - minValue)
return result
#best-time-to-buy-and-sell-stock-ii
from typing import *
class Solution:
def maxProfit(self, prices: List[int]) -> int:
result = 0
for i, value in enumerate(prices):
if i != 0 :
if value > prices[i-1]:
result += value - prices[i-1]
return result
#best-time-to-buy-and-sell-stock-iii
from typing import *
class Solution:
def maxProfit(self, prices: List[int]) -> int:
k = 2
buys = [float("inf") for _ in range(k)]
sells = [0 for _ in range(k)]
for v in prices:
for i in range(k):
if i == 0:
buys[i] = min(buys[i], v)
sells[i] = max(sells[i], v - buys[i])
else:
buys[i] = min(buys[i], v - sells[i-1])
sells[i] = max(sells[i], v - buys[i])
return sells[-1]
#best-time-to-buy-and-sell-stock-iv
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if k == 0 or not prices or len(prices) <= 1:
return 0
if k >= len(prices)//2:
result = 0
for i, v in enumerate(prices):
if i != 0 and v - prices[i-1] > 0:
result += v - prices[i-1]
return result
buys = [float("inf") for _ in range(k)]
sells = [0 for _ in range(k)]
for v in prices:
for i in range(k):
if i == 0:
buys[i] = min(buys[i], v)
sells[i] = max(sells[i], v - buys[i])
else:
buys[i] = min(buys[i], v - sells[i-1])
sells[i] = max(sells[i], v - buys[i])
return sells[-1]
