首页 > 其他分享 >44-best-time-to-buy-and-sell-stock-with-cooldown 力扣 309. 买卖股票的最佳时机包含冷冻期

44-best-time-to-buy-and-sell-stock-with-cooldown 力扣 309. 买卖股票的最佳时机包含冷冻期

时间:2024-11-09 11:57:05浏览次数:5  
标签:sell 309 buy 股票 a1 a3 a2 prices 冷冻

买卖股票系列

【leetcode】40-best-time-to-buy-and-sell-stock 力扣 121. 买卖股票的最佳时机

【leetcode】41-best-time-to-buy-and-sell-stock-ii 力扣 122. 买卖股票的最佳时机 II

【leetcode】42-best-time-to-buy-and-sell-stock-iii 力扣 123. 买卖股票的最佳时机 III

【leetcode】43-best-time-to-buy-and-sell-stock-iv 力扣 188. 买卖股票的最佳时机 IV

【leetcode】44-best-time-to-buy-and-sell-stock-with-cooldown 力扣 309. 买卖股票的最佳时机包含冷冻期

【leetcode】45-best-time-to-buy-and-sell-stock-with-cooldown 力扣 714. 买卖股票的最佳时机包含手续费

开源地址

为了便于大家学习,所有实现均已开源。欢迎 fork + star~

https://github.com/houbb/leetcode

题目

给定一个整数数组prices,其中第 prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:

输入: prices = [1]
输出: 0

提示:

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

v1-DP

整体思路

我们考虑 3 个场景:

// a1: 手上持有股票的最大收益
// a2: 手上不持有股票,并且处于冷冻期中的累计最大收益
// a3: 手上不持有股票,并且不在冷冻期中的累计最大收益

要想计算最大的利润,只需要考虑不持有股票的对比就可。

至于 a1,是为了中转计算。

初始化

a1[0] = -prices[0];

递推公式

a1

a1 什么时候手上会有股票? 必须是买入的时候。

一种是上次就持有;还有一种处于 a3 状态,然后买入。

a1[i] = max(a1[i-1], a3[i-1] - prices[i]);

a2

a2: 手上不持有股票,并且处于冷冻期中的累计最大收益

什么场景会不持有,则处于冷冻期?

就是持有股票,然后直接卖出了?

a2[i] = a1[i-1] + prices[i];

a3

a3: 手上不持有股票,并且不在冷冻期中的累计最大收益

什么场景不持有股票,且不处于冷冻期。

1)此时不能直接卖出,因为会被冷冻;所以

2)昨天分为两个场景:a2 状态;或者 a3 状态

a3[i] = max(a3[i-1], a2[i-1])

完整的伪代码

class Solution {
    
    public int maxProfit(int[] prices) {
        int n = prices.length;
        // a1: 手上持有股票的最大收益   主要是为了计算存储,结果不考虑此场景。
        // a2: 手上不持有股票,并且处于冷冻期中的累计最大收益
        // a3: 手上不持有股票,并且不在冷冻期中的累计最大收益
        int a1[] = new int[n];
        int a2[] = new int[n];
        int a3[] = new int[n];

        // 初始化
        a1[0] = -prices[0];

        for (int i = 1; i < n; ++i) {
            // 持有股票:昨天持有 OR 买入
            a1[i] = Math.max(a1[i-1], a3[i-1] - prices[i]);

            // 手上不持有股票,并且处于冷冻期中的累计最大收益: 必定是卖出
            a2[i] = a1[i-1] + prices[i];

            // 手上不持有股票,并且不在冷冻期中的累计最大收益:  昨天可能是 a3; a2
            a3[i] = Math.max(a2[i-1], a3[i-1]);
        }

        // 手里没有股票对比即可
        return Math.max(a2[n-1], a3[n-1]);
    }
    
}

评价

这一道题严格点说还是比较难的,就是我们必须通过 3 个状态数组来处理。

所以需要前面题目的铺垫。

标签:sell,309,buy,股票,a1,a3,a2,prices,冷冻
From: https://www.cnblogs.com/houbbBlogs/p/18536524

相关文章

  • LeetCode100之买卖股票的最佳时机含冷冻期(309)--Java
    1.问题描述   给定一个整数数组prices,其中第  prices[i] 表示第 i 天的股票价格。​设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):卖出股票后,你无法在第二天买入股票(即冷冻期为1天)。        注意......
  • 42-best-time-to-buy-and-sell-stock-iii 力扣 123. 买卖股票的最佳时机 III
    买卖股票系列【leetcode】40-best-time-to-buy-and-sell-stock力扣121.买卖股票的最佳时机【leetcode】41-best-time-to-buy-and-sell-stock-ii力扣122.买卖股票的最佳时机II【leetcode】42-best-time-to-buy-and-sell-stock-iii力扣123.买卖股票的最佳时机III【le......
  • [极客大挑战 2019]BuyFlag 1
    [极客大挑战2019]BuyFlag1打开实例发现pay.php页面,有提示信息打开源码发现passwordpost提交逻辑burpsuite抓包传参,传入money和password参数,这里password是==弱比较,所以加个字符就可以绕过password=404a&money=100000000回显发现并没有变化注意到学生需要CUIT(Only......
  • 【leetcode】40-best-time-to-buy-and-sell-stock 力扣 121. 买卖股票的最佳时机
    买卖股票系列【leetcode】40-best-time-to-buy-and-sell-stock力扣121.买卖股票的最佳时机【leetcode】41-best-time-to-buy-and-sell-stock-ii力扣122.买卖股票的最佳时机II【leetcode】42-best-time-to-buy-and-sell-stock-iii力扣123.买卖股票的最佳时机III【le......
  • # 20222309 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    1.实验内容一、恶意代码文件类型标识、脱壳与字符串提取对提供的rada恶意代码样本,进行文件类型识别,脱壳与字符串提取,以获得rada恶意代码的编写作者,具体操作如下:(1)使用文件格式和类型识别工具,给出rada恶意代码样本的文件格式、运行平台和加壳工具;(2)使用超级巡警脱壳机等脱壳软件,......
  • [极客大挑战 2019]BuyFlag
    题目链接:https://buuoj.cn/challenges#[极客大挑战2019]BuyFlag打开环境后如下所示。发现右侧中存在一个菜单,并有"PAYFLAG"选项卡,访问其后,响应包如下。HTTP/1.1200OKServer:openrestyDate:Fri,25Oct202415:00:41GMTContent-Type:text/html;charset=UTF-8Con......
  • #2024-2025-1学号20241309《计算机基础与程序设计》第六周学习总结
    作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计这个作业要求在哪里2024-2025-1计算机基础与程序设计第六周作业这个作业的目标作业正文2024-2025-1学号20241309《计算机基础与程序设计》第六周学习总结教材学习内容总结《计算机科学概论......
  • #2024-2025-1学号20241309《计算机基础与程序设计》第五周学习总结
    作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计这个作业要求在哪里2024-2025-1计算机基础与程序设计第五周作业这个作业的目标|作业正文|2024-2025-1学号20241309《计算机基础与程序设计》第五周学习总结教材学习内容总结《计算机科学概论》......
  • # 20222309 2024-2025-1 《网络与系统攻防技术》实验三实验报告
    1.实验内容1、实践内容(1)正确使用msf编码器,veil-evasion,自己利用shellcode编程等免杀工具或技巧(2)通过组合应用各种技术实现恶意代码免杀(3)用另一电脑实测,在杀软开启的情况下,可运行并回连成功,注明电脑的杀软名称与版本2、实验要求(1)杀软是如何检测出恶意代码的?基于特征......
  • # 20222309 2024-2025-1 《网络与系统攻防技术》实验二实验报告
    1.实验内容1、实验目标(1)使用netcat获取主机操作Shell,cron启动某项任务(任务自定)PS:cron是linux下用来周期性的执行某种任务或等待处理某些事件的一个守护进程(2)使用socat获取主机操作Shell,任务计划启动(3)使用MSFmeterpreter(或其他软件)生成可执行文件(后门),利用ncat或socat......