class Solution:
def maxProfit(self, prices: List[int]) -> int:
maxP = 0 #初始为0
for i in range(len(prices)):
for j in range(i+1, len(prices)):
maxP = max(maxP, prices[j] - prices[i]) #求最大利润
return maxP
解法二:一次遍历
每次先更新最低价格,然后用当前价格减最低价格得到当前利润,并更新最高利润
class Solution:
def maxProfit(self, prices: List[int]) -> int:
min_price, max_profit = sys.maxsize, 0
#一次遍历,从前往后,每次更新最小值,用当前价格减去最小值计算差价,遇到最大价格则更新
for i in range(len(prices)):
min_price = min(min_price, prices[i])
max_profit = max(max_profit, prices[i] - min_price)
return max_profit
解法三:状态机dp
即k=1,直接套状态转移方程,根据 base case,可以做一些化简:
1 ≤ i < n
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i])
= max(dp[i-1][1][1], -prices[i]) #解释:k = 0 的 base case,所以 dp[i-1][0][0] = 0。
现在发现 k 都是 1,不会改变,即 k 对状态转移已经没有影响了。 可以进行进一步化简去掉所有 k:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n == 0:
return 0
dp = [[0] *2 for _ in range(n+1)]
#用i=0表示初始条件,即i=1为第1天
for i in range(n+1):
if i == 0:
dp[i][0] = 0
dp[i][1] = -sys.maxsize
continue
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1])
dp[i][1] = max(dp[i-1][1], -prices[i-1])
return dp[n][0]