算法打卡day42

本文主要是介绍算法打卡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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！