代码随想录算法训练营第四十九天|121. 买卖股票的最佳时机、122.买卖股票的最佳时机II

**代码随想录算法训练营第四十九天**

##买卖股票的最佳时机### 题目描述给定一个数组 `prices`，其中每个元素代表一天股价。请写出一个函数 `maxProfit`，返回最大可能的利润。

### 示例* 输入:`[7,1,5,3,6,8]`
输出:`7`（买入于第2 天，卖出于第7 天）
* 输入:`[7,6,4,3,1]`
输出:`0`（没有可能的利润）

### 解决方案我们可以使用动态规划来解决这个问题。假设 `dp[i][j]` 表示在第 `i` 天结束时，持有股票 `j` 的最大利润。

* 如果我们不持有股票，则 `dp[i][0] = dp[i-1][0] + max(0, prices[i] - prices[i-1])`
* 如果我们持有股票，则 `dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])`

最终答案是 `max(dp[-1][0], dp[-1][1])`。

###代码实现

def maxProfit(prices):
 if not prices:
 return0 n = len(prices)
 # 动态规划表格，行数为天数，列数为持有股票的状态 dp = [[0] *2 for _ in range(n)]
 # 初始化第一行 dp[0][0] = max(0, prices[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], dp[i-1][0] - prices[i])
 # 最终答案是最大利润 return max(dp[-1][0], dp[-1][1])

# 测试用例print(maxProfit([7,1,5,3,6,8])) # 输出：7print(maxProfit([7,6,4,3,1])) # 输出：0

##买卖股票的最佳时机II### 题目描述给定一个数组 `prices`，其中每个元素代表一天股价。请写出一个函数 `maxProfit`，返回最大可能的利润。

### 示例* 输入:`[1,2,3,4,5]`
输出:`4`（买入于第2 天，卖出于第5 天）
* 输入:`[7,6,4,3,1]`
输出:`0`（没有可能的利润）

### 解决方案我们可以使用动态规划来解决这个问题。假设 `dp[i][j]` 表示在第 `i` 天结束时，持有股票 `j` 的最大利润。

* 如果我们不持有股票，则 `dp[i][0] = dp[i-1][0] + max(0, prices[i] - prices[i-1])`
* 如果我们持有股票，则 `dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])`

最终答案是 `max(dp[-1][0], dp[-1][1])`。

###代码实现

def maxProfit(prices):
 if not prices:
 return0 n = len(prices)
 # 动态规划表格，行数为天数，列数为持有股票的状态 dp = [[0] *2 for _ in range(n)]
 # 初始化第一行 dp[0][0] = max(0, prices[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], dp[i-1][0] - prices[i])
 # 最终答案是最大利润 return max(dp[-1][0], dp[-1][1])

# 测试用例print(maxProfit([1,2,3,4,5])) # 输出：4print(maxProfit([7,6,4,3,1])) # 输出：0

以上是买卖股票的最佳时机和买卖股票的最佳时机II的解决方案。