当前位置: 首页 > news >正文

力扣123. 买卖股票的最佳时机 III

动态规划

  • 思路:
    • 最多可以完成两笔交易,因此任意一天结束后,会处于5种状态:
      • 未进行任何操作;
      • 只进行了一次买操作;
      • 进行了一次买操作和一次卖操作;
      • 再完成了一次交易之后,进行了一次买操作;
      • 完成了两次交易;
    • 第 1 种状态利润未发生变化,不记录其状态;
    • 假设其他四种状态的最大利润分别是 buy1,sell1,buy2,sell2;
    • 对应的状态转移方程:
      • 第 i 天状态为 buy1 可以是:
        • 第 i - 1 天是 buy1,第 i 天不操作,即 buy1';
        • 第 i 天进行买操作,第 i - 1 天未进行任何操作 -prices[i];
        • 则 buy1 = max(buy1', -prices[i]);
      • 第 i 天状态是 sell1 可以是:
        • 第 i - 1 天是 sell1,第 i 天不操作,即 sell1';
        • 第 i - 1 天是 buy1,第 i 天卖出,即 buy1' + prices[i];
        • 则 sell1 = max(sell1', buy1' + prices[i]);
      • 第 i 天状态是 buy2 可以是:
        • 第 i - 1 天是 buy2,第 i 天不操作,即 buy2';
        • 第 i - 1 天是 sell1,第 i 天买入,即 sell1' - prices[i];
        • 则 buy2 = max(buy2', sell1' - prices[i]);
      • 第 i 天状态是 sell2 可以是:
        • 第 i - 1 天是 sell2,第 i 天不操作,即 sell2';
        • 第 i - 1 天是 buy2,第 i 天卖出,即 buy2' + prices[i];
        • 则 sell2 = max(sell2', buy2' + prices[i]);
      • 同一天买入卖出对收益不会产生影响,在状态转移时,可以直接根据第 i 天计算出的值进行状态转移;
    • 边界条件第 0 天:
      • buy1 = -prices[0]
      • sell1 = 0
      • buy2 = -prices[0]
      • sell2 = 0
    • 从 i = 1 开始进行动态规划,最终 sell2 的结果即为所求的最大收益;
class Solution {
public:int maxProfit(vector<int>& prices) {int size = prices.size();int buy1 = -prices[0];int sell1 = 0;int buy2 = -prices[0];int sell2 = 0;for (int i = 0; i < size; ++i) {buy1 = std::max(buy1, -prices[i]);sell1 = std::max(sell1, buy1 + prices[i]);buy2 = std::max(buy2, sell1 - prices[i]);sell2 = std::max(sell2, buy2 + prices[i]);}return sell2;}
};

相关文章:

力扣123. 买卖股票的最佳时机 III

动态规划 思路&#xff1a; 最多可以完成两笔交易&#xff0c;因此任意一天结束后&#xff0c;会处于5种状态&#xff1a; 未进行任何操作&#xff1b;只进行了一次买操作&#xff1b;进行了一次买操作和一次卖操作&#xff1b;再完成了一次交易之后&#xff0c;进行了一次买操…...

Vue3:vue-cli项目创建

一、node.js检测或安装&#xff1a; node -v node.js官方 二、vue-cli安装&#xff1a; npm install -g vue/cli # OR yarn global add vue/cli/*如果安装的时候报错&#xff0c;可以尝试一下方法 删除C:\Users**\AppData\Roaming下的npm和npm-cache文件夹 删除项目下的node…...

C# .Net学习笔记—— 异步和多线程(Task)

一、概念 Task是DotNet3.0之后所推出的一种新的使用多线程的方式&#xff0c;它是基于ThreadPool线程进行封装的。 二、使用多线程的时机 任务能够并发运行的时候&#xff0c;提升速度&#xff1b;优化体验 三、基本使用方法 private void button5_Click(object sender, Ev…...

Python从入门到网络爬虫(读写Excel详解)

前言 Python操作Excel的模块有很多&#xff0c;并且各有优劣&#xff0c;不同模块支持的操作和文件类型也有不同。最常用的Excel处理库有xlrd、xlwt、xlutils、xlwings、openpyxl、pandas&#xff0c;下面是各个模块的支持情况&#xff1a; 工具名称.xls.xlsx获取文件内容写入…...

Mysql之子查询、连接查询(内外)以及分页查询

目录 一.案例&#xff08;接上篇博客&#xff09; 09&#xff09;查询学过「张三」老师授课的同学的信息 10&#xff09;查询没有学全所有课程的同学的信息 11&#xff09;查询没学过"张三"老师讲授的任一门课程的学生姓名 12&#xff09;查询两门及其以上不及格课程…...

计算机的存储单位

在计算机中&#xff0c;只能识别二进制。 byte是1个字节&#xff0c;是8个比特位&#xff0c;所以byte可以存储的最大值是&#xff1a;01111111&#xff0c;byte是 [-128 ~ 127] 共可以标识256个不同的数字。 1字节 8bit&#xff08;8比特&#xff09;--> 1byte 8bit 类…...

设备树文件中的设备节点

一. 简介 前面几篇文章学习了 关于设备树文件的编译&#xff0c;设备树文件的调用。 本文开始学习 设备树文件的语法。具体学习设备节点与标准属性。 二. 设备树文件之设备节点与标准属性 1. 设备节点 设备树 是采用树形结构来描述板子上的设备信息的文件&#xff0c;每…...

文件管理工具.netcore资源文件管理

文件管理工具 怎么快速有效的管理我的文件包括文件夹&#xff0c;需求功能是 模糊搜索显示匹配的文件夹或文件数据 快速打开文件夹位置 在windows直接查看搜索速度太慢&#xff0c;范围宽泛&#xff0c;整理所需资源文件名和文件本机路径保存在数据库&#xff0c;可以在数据库中…...

go-carbon v2.3.4 发布,轻量级、语义化、对开发者友好的 Golang 时间处理库

carbon 是一个轻量级、语义化、对开发者友好的 golang 时间处理库&#xff0c;支持链式调用。 目前已被 awesome-go 收录&#xff0c;如果您觉得不错&#xff0c;请给个 star 吧 github.com/golang-module/carbon gitee.com/golang-module/carbon 安装使用 Golang 版本大于…...

vue3 内置组件

文章目录 前言一、过渡效果相关的组件1、Transition2、TransitionGroup 二、状态缓存组件&#xff08;KeepAlive&#xff09;三、传送组件&#xff08;Teleport &#xff09;四、异步依赖处理组件&#xff08;Suspense&#xff09; 前言 在vue3中 其提供了5个内置组件 Transiti…...

MFC如何动态创建button按钮并添加点击事件

在MFC中&#xff0c;可以使用CButton类来动态创建按钮。下面是一个示例代码&#xff0c;演示了如何动态创建按钮并添加点击事件&#xff1a; 在对话框类的头文件中声明按钮变量&#xff1a; CButton m_btnDynamic;在对话框的OnInitDialog()函数中使用Create()函数创建按钮&am…...

Qt - QML框架

文章目录 1 . 前言2 . 框架生成3 . 框架解析3.1 qml.pro解析3.2 main.cpp解析3.3 main.qml解析 4 . 总结 【极客技术传送门】 : https://blog.csdn.net/Engineer_LU/article/details/135149485 1 . 前言 什么是QML&#xff1f; QML是一种用户界面规范和编程语言。它允许开发人员…...

Python+Flask+MySQL的图书馆管理系统【附源码,运行简单】

PythonFlaskMySQL的图书馆管理系统【附源码&#xff0c;运行简单】 总览 1、《的图书馆管理系统》1.1 方案设计说明书设计目标需求分析工具列表 2、详细设计2.1 登录2.2 注册2.3 程序主页面2.4 图书新增界面2.5 图书信息修改界面2.6 普通用户界面2.7 其他功能贴图 3、下载 总览…...

Module-Federation[微前端]

Module-Federation 微前端简介我们为什么没有延续使用【乾坤】使用Module-Federation 优/缺EMP 优EMP 缺图解DEMO详解`Tips:` [文件资源](https://download.csdn.net/download/alnorthword/88699315)微前端简介 微前端是借鉴了微服务的理念,将一个庞大的应用拆分成多个独立灵活…...

Spring 动态数据源事务处理

在一般的 Spring 应用中,如果底层数据库访问采用的是 MyBatis,那么在大多数情况下,只使用一个单独的数据源,Spring 的事务管理在大多数情况下都是有效的。然而,在一些复杂的业务场景下,如需要在某一时刻访问不同的数据库,由于 Spring 对于事务管理实现的方式,可能不能达…...

WSL2-Ubuntu22.04子系统图形化界面搭建与远程桌面连接

提示&#xff1a;文中不提供WSL2子系统搭建步骤&#xff0c;假定子系统已建立好&#xff1a; 文章目录 检查WSL子系统状态图形化界面安装远程桌面连接可能遇到的相关问题xrdp状态异常远程桌面黑屏 检查WSL子系统状态 wsl -l -v如下图所示为正常 图形化界面安装 以此执行如下…...

【sklearn练习】model常用属性和功能

介绍 scikit-learn 中的机器学习模型&#xff08;estimator&#xff09;通常具有一组常用属性和功能&#xff0c;这些属性和功能可以用于训练、评估和使用模型。以下是一些常见的模型属性和功能&#xff1a; 常见属性&#xff1a; coef_&#xff1a;对于线性模型&#xff08;…...

IO类day01

File类 File类的每一个实例可以表示硬盘(文件系统)中的一个文件或目录(实际上表示的是一个抽象路径) 使用File可以做到: 1:访问其表示的文件或目录的属性信息,例如:名字,大小,修改时间等等 2:创建和删除文件或目录 3:访问一个目录中的子项 但是File不能访问文件数据. pu…...

软件测试大作业||测试计划+测试用例+性能用例+自动化用例+测试报告

xxx学院 2023—2024 学年度第二学期期末考试 《软件测试》&#xff08;A&#xff09;试题&#xff08;开卷&#xff09; 题目&#xff1a;以某一 web 系统为测试对象&#xff0c;完成以下文档的编写&#xff1a; &#xff08;满分 100 分&#xff09; &#xff08;1&am…...

适用于任何公司的网络安全架构

1.第一等级:基础级 优势 可防范基本有针对性的攻击&#xff0c;使攻击者难以在网络上推进。将生产环境与企业环境进行基本隔离。 劣势 默认的企业网络应被视为潜在受损。普通员工的工作站以及管理员的工作站可能受到潜在威胁&#xff0c;因为它们在生产网络中具有基本和管理…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...

uni-app学习笔记三十五--扩展组件的安装和使用

由于内置组件不能满足日常开发需要&#xff0c;uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件&#xff0c;需要安装才能使用。 一、安装扩展插件 安装方法&#xff1a; 1.访问uniapp官方文档组件部分&#xff1a;组件使用的入门教程 | uni-app官网 点击左侧…...

从实验室到产业:IndexTTS 在六大核心场景的落地实践

一、内容创作&#xff1a;重构数字内容生产范式 在短视频创作领域&#xff0c;IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色&#xff0c;生成的 “各位吴彦祖们大家好” 语音相似度达 97%&#xff0c;单条视频播放量突破百万…...

goreplay

1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具&#xff0c;可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长&#xff0c;测试它所需的工作量也会呈指数级增长。GoRepl…...