本文主要是介绍算法打卡day42，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今日任务：
1）121. 买卖股票的最佳时机
2）122.买卖股票的最佳时机II
3）复习day17
121. 买卖股票的最佳时机
题目链接：121. 买卖股票的最佳时机 - 力扣（LeetCode）
给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。示例 1： 输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2： 输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划之 LeetCode：121.买卖股票的最佳时机1哔哩哔哩bilibili
思路：
这是一道经典的股票买卖问题，可以通过动态规划来解决。我们可以维护两个变量来记录当前的最低买入价格和最大利润。遍历股票价格数组，对于每一天的股票价格，我们更新最低买入价格和最大利润：
- 如果当前股票价格低于最低买入价格，则更新最低买入价格为当前价格；
- 否则，计算当前股票价格与最低买入价格之差，更新最大利润为当前利润与已记录的最大利润的较大值。
class Solution:def maxProfit(self, prices: List[int]) -> int:if not prices:return 0# 初始化最低买入价格和最大利润min_price = prices[0]max_profit = 0# 遍历股票价格数组for price in prices[1:]:# 更新最低买入价格min_price = min(min_price, price)# 计算当前利润profit = price - min_price# 更新最大利润max_profit = max(max_profit, profit)return max_profit
122.买卖股票的最佳时机II
题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）
文章讲解：代码随想录 (programmercarl.com)
视频讲解：动态规划，股票问题第二弹 | LeetCode：122.买卖股票的最佳时机II哔哩哔哩bilibili
思路：
我们可以用动态规划来解决这个问题。在这个问题中，我们只关心最终能够获得的利润，而不需要具体的交易路径。因此，我们可以定义两个状态变量：
hold：表示当前持有股票时的最大利润。not_hold：表示当前不持有股票时的最大利润。对于每一天，我们有三种操作：
- 保持持有状态，即不卖出，这样利润不变。
- 卖出股票，这样我们的利润将增加当前股票的价格。
- 买入股票，这样我们的利润将减少当前股票的价格。
我们的目标是选择操作使得最终的利润最大化。因此，我们可以通过比较这三种操作的结果来更新状态变量
hold和not_hold。具体步骤如下：
- 首先，我们初始化
hold为负无穷，表示当前不可能持有股票，而not_hold为 0，表示当前没有股票，利润为 0。- 然后，我们遍历每一天的股票价格，对于每一天，我们都更新
hold和not_hold。
- 如果选择保持持有状态，即不卖出，则当前持有股票时的最大利润为上一状态的
hold。- 如果选择卖出股票，则当前不持有股票时的最大利润为上一状态的
hold加上当前股票价格。- 如果选择买入股票，则当前持有股票时的最大利润为上一状态的
not_hold减去当前股票价格。- 最终，我们返回
not_hold，因为在最后一天，我们希望不持有股票以获取最大利润。
class Solution:def maxProfit(self, prices: List[int]) -> int:if not prices:return 0# 定义状态变量hold = float('-inf') # 持有股票时的最大利润not_hold = 0 # 不持有股票时的最大利润# 遍历股票价格数组for price in prices:# 计算当前持有股票时的最大利润hold = max(hold, not_hold - price)# 计算当前不持有股票时的最大利润not_hold = max(not_hold, hold + price)return not_hold
注意这里的hold（持有股票），我可以选择继续持有上一个状态的股票，就是继承上一状态的hold，也可以选择在当天持有股票，如果持有当前股票，那么此刻hold为上一状态不持有股票的金额-当前股票价钱，比较这两个hold，谁大选择谁
no_hold（不持有股票），我们可以选择卖掉已经持有的股票，那么no_hold为上一状态持有股票的金额+当前股票价格，另一种我们可以选择继续继承上一状态的不持有，比较这两个no_hold谁更大
这篇关于算法打卡day42的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
