当前位置: 首页 > 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;因为它们在生产网络中具有基本和管理…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

GraphRAG优化新思路-开源的ROGRAG框架

目前的如微软开源的GraphRAG的工作流程都较为复杂&#xff0c;难以孤立地评估各个组件的贡献&#xff0c;传统的检索方法在处理复杂推理任务时可能不够有效&#xff0c;特别是在需要理解实体间关系或多跳知识的情况下。先说结论&#xff0c;看完后感觉这个框架性能上不会比Grap…...