## leetcode：买卖股票的最佳时机（python）

LeetCode 股票 最佳 买卖 最佳时机

## 2. 1 常规思路

### 2.1 Python代码

``````class Solution:
def maxProfit(self, prices: List[int]) -> int:
minPrice = float("inf")
maxProfit = 0
if len(prices) == 0:
return 0
for num in prices:
if num < minPrice:
minPrice = num
if num - minPrice > maxProfit:
maxProfit = num - minPrice
return maxProfit
``````

## 2.2 动态规划

### 2.2 动态规划代码

``````class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
n = len(prices)
dp = [[0 for i in range(2)] for i in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1,n):
dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1],-prices[i])
return dp[n-1][0]
``````

### 动态优化优化代码

``````class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
n = len(prices)
dp_0_0 = 0 # 不持有
dp_0_1 = -prices[0] # 持有
for i in range(1,n):
dp_0_0 = max(dp_0_0,dp_0_1 + prices[i])
dp_0_1 = max(dp_0_1,-prices[i])
return dp_0_0
``````

https://blog.csdn.net/ggdhs/article/details/92380969