买卖股票的最佳时机III
题目链接
买卖股票的最佳时机III
题目描述
注意点
- 1 <= prices.length <= 100000
- 0 <= prices[i] <= 100000
- 不能同时参与多笔交易(必须在再次购买前出售掉之前的股票)
- 最多可以完成 两笔 交易
解答思路
- 本题最多可以完成两笔交易,所以在任意一天,都会有五种状态,分别是无操作、第一次买入、第一次卖出、第二次买入、第二次卖出。需要注意的是,当天同时买入卖出是无意义的,利润不会改变,仅仅是增加了交易次数,不在考虑范围之内。同时无操作的利润始终为0,可以忽略不记,所以将每一天都分割成其余四种状态
- 关键是怎么通过第i - 1天推出第i天四种状态的最大利润,可以分为以下几种
- 当处于第一次买入的状态,其可能是当天购入也可能是之前就已经购入,取决于哪天购买的成本更低,所以dp[i][0] = Math.max(dp[i - 1][0], -prices[i]),注意当天购入的话需要花费prices[i]的成本,所以为负数
- 当处于第一次卖出的状态,其可能是当天买出也可能是之前就已经卖出,取决于哪天卖出的利润更高,所以dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]),dp[i - 1][0]是第一次购买最低的成本,其可以保证当天卖出在前i天当中所得到的利润是最大的
- 当处于第二次买入的状态,其与第一次买入的状态类似,区别是第一次已经交易成功了,所以如果当天买入的话dp[i][2]的值还要加上第一次交易所得到的最大利润,也就是dp[i - 1][1],所以dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i])
- 当处于第二次卖入的状态,其与第二次卖出的状态类似,dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i])
- 需要注意的是,dp[0][2]与dp[0][0]一样,初始需要给默认值-prices[0],在第一次交易未完成时,dp[i][2]实际上始终与dp[i][0]相同,dp[i][3]与dp[i][1]也是如此,实际上此时第二次交易也是第一次交易(因为dp[i - 1][1]始终都为0,此时dp[i][2] = Math.max(dp[i - 1][2], - prices[i]))。当第一次交易完成时,dp[i][2]就需要在第一次交易获得利润的基础上进行考虑,其购买的成本会变为dp[i - 1][1] - prices[i]
代码
class Solution {public int maxProfit(int[] prices) {int n = prices.length;// 二维数组,dp[i][j]表示第i天时处于第j中状态的最大利润/*** j有以下四种状态* 0:第一次买入股票* 1:第一次卖出股票(也就是完成第一次交易)* 2:第二次买入股票* 3:第二次卖出股票(也就是完成第二次交易)* 不做任何操作也是一种状态,但是对结果无影响不考虑*/int[][] dp = new int[n][4];dp[0][0] = -prices[0];dp[0][2] = -prices[0];for (int i = 1; i < n; i++) {// 第i天购买或者之前就已购买,取购买花费更低的成本dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);// 第i天卖出或者之前就已卖出,取卖出得到更高的利润dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);// 第i天购买或者之前就已购买,取购买花费更低的成本,第二次交易还要加上第一次交易所得的利润dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i]);// 第i天卖出或者之前就已卖出,取卖出得到更高的利润dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i]);}return Math.max(dp[n - 1][1], dp[n - 1][3]);}
}
关键点
- 动态规划的思想
- 每天买卖股票的四种状态
- 怎么根据dp[i - 1][j]推出dp[i][j]
相关文章:
买卖股票的最佳时机III
题目链接 买卖股票的最佳时机III 题目描述 注意点 1 < prices.length < 1000000 < prices[i] < 100000不能同时参与多笔交易(必须在再次购买前出售掉之前的股票)最多可以完成 两笔 交易 解答思路 本题最多可以完成两笔交易,…...
fastlio2 保存每帧的点云和每帧的里程计为单独的文件做后端回环优化和手动回环优化
为了 提供数据做后端回环优化和手动回环优化,需要保存每帧的点云和每帧的里程计为单独的文件,并且需要保存的名字为ros时间戳。 效果很好,比我自己写的手动回环模块好用 // This is an advanced implementation of the algorithm described in the // following paper: /…...
【线段树】【前缀和】:1687从仓库到码头运输箱子
本题简单解法 C前缀和算法的应用:1687从仓库到码头运输箱子 本文涉及的基础知识点 C算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 线段树 LeetCode1687从仓库到码头运输箱子 你有一辆货运卡车,你需要用这一辆车…...
[AIGC] 实现博客平台的推荐排行榜
推荐排行榜是许多网站和平台的重要特性,它可以把最受欢迎或最具价值的内容展示给用户。本文将详细介绍如何为博客网站实现一个推荐排行榜。 文章目录 一、选择推荐指标二、收集数据三、设计排行榜算法四、显示推荐排行榜五、demo总结 一、选择推荐指标 实现推荐排行…...
C++利用键值对计算某一个数对应的最值及其索引位置
目录 一、算法概述二、代码实现1、计算最值2、计算最值及其索引 三、结果展示 本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT。 一、算法概述 类似下图所示,计算第一列中1或2对应的最…...
conda修改默认安装python版本为指定版本
1.查看conda中当前的python版本号: 打开Anaconda Powershell Prompt 输入python -V 回车会输出版本号 2.查看conda所支持的python版本,并选择指定版本安装 选择一个3.9.13版本的进行安装 安装命令: conda install python3.9.13 如果一直卡在这个画面,请使用管理员权限运行…...
显示学习番外篇(基于树莓派Pico) -- 游戏(TODO)
来自:11.4. 飞行小鸟 — mPython掌控 2.2.0 documentation (TODO)...
顺序表实战——基于顺序表的通讯录
前言:本篇文章主要是利用顺序表作为底层, 实现一个通讯录。偏向于应用, 对于已经学习过c的友友们可能没有难度了已经。没有学习过c的友友, 如果顺序表不会写, 或者说没有自己实现过, 请移步学习顺序表相关内…...
创建型模式--1.单例模式【巴基速递】
1. 巴基的订单 在海贼世界中,巴基速递是巴基依靠手下强大的越狱犯兵力,组建的集团海贼派遣公司,它的主要业务是向世界有需要的地方输送雇佣兵(其实是不干好事儿)。 自从从特拉法尔加罗和路飞同盟击败了堂吉诃德家族 &…...
用 Wireshark 解码 H.264
H264,你不知道的小技巧-腾讯云开发者社区-腾讯云 这篇文章写的非常好 这里仅做几点补充 init.lua内容: -- Set enable_lua to false to disable Lua support. enable_lua trueif not enable_lua thenreturn end-- If false and Wireshark was start…...
鸿蒙TypeScript学习第10天:【String(字符串)】
1、TypeScript String(字符串) String 对象用于处理文本(字符串)。 语法 var txt new String("string"); 或者更简单方式: var txt "string"; 2、String 对象属性 下表列出了 String 对象支…...
【201】Java8读取JSON树形结构并插入到MySQL数据库表中
我写了一个 maven 项目的 Demo,用来演示 JAVA8 如何读取 JSON 文件树形结构,并将这种树形结构保存到 MySQL 中。 json文件 city.json {"name": "山东省","sub": [{"name": "青岛市","sub"…...
AI“复活”:慰藉心灵还是触碰禁忌?一文看懂技术与伦理的较量|TodayAI
随着人工智能(AI)技术的迅猛发展,其应用领域也越来越广泛,不仅仅局限于数据分析、机器人自动化等传统领域,更是延伸到了一些人们曾经认为只存在于科幻小说中的领域。近年来,使用AI技术“复活”逝者的概念&a…...
Jackson @JsonUnwrapped注解扁平化 序列化反序列化数据
参考资料 Jackson 2.x 系列【7】注解大全篇三JsonUnwrapped 以扁平的数据结构序列化/反序列化属性Jackson扁平化处理对象 目录 一. 前期准备1.1 前端1.2 实体类1.3 Controller层 二. 扁平化序列反序列化数据2.1 序列化数据2.2 反序列化数据 三. 前缀后缀处理属性同名四. Map数…...
日期时间相关的类
分界线jdk8 jdk8之前和之后分别提供了一些日期和时间的类,推荐使用jdk8之后的日期和时间类 Date类型 这是一个jdk8之前的类型,其中有很多方法已经过时了,选取了一些没有过时的API //jdk1.8之前的日期 Date Date date new Date(); // 从1970年…...
微信小程序脚本的执行顺序
在小程序中的脚本执行顺序和浏览器中有所不同。 小程序的执行的入口文件是 app.js 。 并且会根据其中 require 的模块顺序决定文件的运行顺序,代码是一个 app.js 示例。 app.js /* a.js console.log(a.js) */ var a require(./a.js) console.log(app.js)/* b.js co…...
zabbix监控警告
监控概述 对服务的管理,不能仅限于可用性。 还需要服务可以安全、稳定、高效地运行。 监控的目的:早发现、早治疗。 被监控的资源类型: 公开数据:对外开放的,不需要认证即可获取的数据 私有数据:对外不…...
YOLOv9架构图分享
YOLOv9是YOLO (You Only Look Once)系列实时目标检测系统的最新迭代。它建立在以前的版本之上,结合了深度学习技术和架构设计的进步,以在目标检测任务中实现卓越的性能。通过将可编程梯度信息(PGI)概念与广义ELAN (GELAN)架构相结合,YOLOv9在…...
全自动封箱机的工作原理:科技与效率的完美结合
随着科技的不断发展,越来越多的自动化设备走进了我们的日常生活和工业生产中。其中,全自动封箱机作为物流包装领域的重要一环,凭借其高效、精准的工作性能,正逐渐成为提升生产效率、降低劳动成本的得力助手。星派就来与大家深入探…...
【管理咨询宝藏48】AA银行信息科技提升分析报告
本报告首发于公号“管理咨询宝藏”,如需阅读完整版报告内容,请查阅公号“管理咨询宝藏”。 【管理咨询宝藏48】AA银行信息科技提升分析报告 【格式】PPT版本,可编辑 【关键词】战略规划、商业分析、管理咨询 【强烈推荐】这是一套市面上非常…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...

