Leetcode 121 买卖股票的最佳时机
题意理解:
给定一个数组
prices
,它的第i
个元素prices[i]
表示一支给定股票第i
天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回
0
。
注意:这里只有一只股票,只进行一次买卖,求最大利益。
所以:对于每一天,都有两个状态:持有股票、不持有股票
这里定义一个二维dp数组:dp[0]表示持有股票能获得的最大收益,dp[0]表示不持有股票能获得最大大受益。
对于不持有股票的状态:包含当天卖出
持有股票状态:包含当前买入
解题思路:
定义二维dp[]数组:
dp[i][0]:表示持有股票能获得的最大收益
dp[i][1]:表示不持有股票能获得最大大受益
1.初始化
dp[0][0]=-price[0];//买入所以当前收益为负
dp[0][1]=0;//无交易,无收益
2.递推公式
dp[i][0]=max(之前买入,当前买入)=max(dp[i-1][0],-prices[i])
dp[i][1]=max(之前卖出,今天卖出)=max(dp[i-1][1],dp[i-1][0]+prices[i])
1.解题
public int maxProfit(int[] prices) {int[][] dp=new int[prices.length][2];dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<prices.length;i++){dp[i][0]=Math.max(dp[i-1][0],-1*prices[i]);dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);}return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);}
2.分析
时间复杂度:O(n)
空间复杂度:O(2n)
相关文章:
Leetcode 121 买卖股票的最佳时机
题意理解: 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交…...
SQL语言复习-----1
1,前言 SQL是计算机的一门基础语言,无论在开发还是数据库管理上都是非常重要,最近总结归纳了一下相关知识,记录如下。 2,归纳 SQL是结构化查询语言。 关系数据库有三级模式结构。 基本表和视图一样都是关系。 举例…...

爬虫2—用爬虫爬取壁纸(想爬多少张爬多少张)
先看效果图: 我这个是爬了三页的壁纸60张。 上代码了。 import requests import re import os from bs4 import BeautifulSoupcount0 img_path "./壁纸图片/"#指定保存地址 if not os.path.exists(img_path):os.mkdir(img_path) headers{ "User-Ag…...
学习Android的第九天
目录 Android Button 按钮 基本的按钮 StateListDrawable 范例 使用颜色值绘制圆角按钮 自制水波纹效果 Android ImageButton 图片按钮 ImageButton 不同状态下的 ImageButton Android RadioButton 单选按钮 RadioButton 获得选中的值 Android Button 按钮 在 And…...
课时21:内置变量_脚本相关
2.4.1 脚本相关 学习目标 这一节,我们从 基础知识、简单实践、小结 三个方面来学习 基础知识 脚本相关的变量解析 序号变量名解析1$0获取当前执行的shell脚本文件名2$n获取当前执行的shell脚本的第n个参数值,n1…9,当n为0时表示脚本的文…...
ubuntu22.04@laptop OpenCV Get Started: 006_annotating_images
ubuntu22.04laptop OpenCV Get Started: 006_annotating_images 1. 源由2. line/circle/rectangle/ellipse/text 应用Demo3 image_annotation3.1 C应用Demo3.2 Python应用Demo3.3 重点过程分析3.3.1 划线3.3.2 画圆3.3.3 矩形3.3.4 椭圆3.3.5 文字 4. 总结5. 参考资料 1. 源由 …...

【制作100个unity游戏之23】实现类似七日杀、森林一样的生存游戏10(附项目源码)
本节最终效果演示 文章目录 本节最终效果演示系列目录前言快捷栏绘制UI代码控制快捷列表信息 源码完结 系列目录 前言 欢迎来到【制作100个Unity游戏】系列!本系列将引导您一步步学习如何使用Unity开发各种类型的游戏。在这第23篇中,我们将探索如何制作…...

uniapp vue3怎么调用uni-popup组件的this.$refs.message.open() ?
vue2代码 <!-- 提示信息弹窗 --><uni-popup ref"message" type"message"><uni-popup-message :type"msgType" :message"messageText" :duration"2000"></uni-popup-message></uni-popup>typ…...

【深度学习:语义分割】语义分割简介
【深度学习:语义分割】语义分割简介 什么是图像分割?了解语义分割数据采集语义分割的深度学习实现全卷积网络上采样跳跃连接U-NetDeepLab多尺度物体检测金字塔场景解析网络(PSPNet) 语义分割的应用医学影像自动驾驶汽车农业图片处…...

前端开发_AJAX基本使用
AJAX概念 AJAX是异步的JavaScript和XML(Asynchronous JavaScript And XML)。 简单点说,就是使用XMLHttpRequest对象与服务器通信。 它可以使用JSON,XML,HTML和text文本等格式发送和接收数据。 AJAX最吸引人的就是它的“异步"特性&am…...

OnlyOffice-8.0版本深度测评
OnlyOffice 是一套全面的开源办公协作软件,不断演进的 OnlyOffice 8.0 版本为用户带来了一系列引人瞩目的新特性和功能改进。OnlyOffice 8.0 版本在功能丰富性、安全性和用户友好性上都有显著提升,为用户提供了更为强大、便捷和安全的文档处理和协作环境…...

【Go】一、Go语言基本语法与常用方法容器
GO基础 Go语言是由Google于2006年开源的静态语言 1972:(C语言) — 1983(C)—1991(python)—1995(java、PHP、js)—2005(amd双核技术 web端新技术飞速发展&…...

杨中科 ASP.NETCORE 高级14 SignalR
1、什么是websocket、SignalR 服务器向客户端发送数据 1、需求:Web聊天;站内沟通。 2、传统HTTP:只能客户端主动发送请求 3、传统方案:长轮询(Long Polling)。缺点是?(1.客户端发送请求后&…...

哪家洗地机比较好用?性能好的洗地机推荐
在众多功能中,我坚信洗地机的核心依旧是卓越的清洁能力以及易于维护的便捷性,其他的附加功能可以看作是锦上添花,那么如何找到性能好的洗地机呢?我们一起看看哪些洗地机既能确保卫生效果还能使用便利。 洗地机工作原理࿱…...
学习与非学习
学习与非学习是人类和动物行为表现中的两种基本形式,它们在认知过程和行为适应上有着根本的区别。理解这两者之间的差异对于把握认知发展、心理学以及教育学等领域的核心概念至关重要。 学习 学习是一个获取新知识、技能、态度或价值观的过程,它导致行为…...
牛客网SQL进阶127: 月总刷题数和日均刷题数
官网链接: 月总刷题数和日均刷题数_牛客题霸_牛客网现有一张题目练习记录表practice_record,示例内容如下:。题目来自【牛客题霸】https://www.nowcoder.com/practice/f6b4770f453d4163acc419e3d19e6746?tpId240 0 问题描述 基于练习记录表…...
19:Web开发模式与MVC设计模式-Java Web
目录 19.1 Java Web开发模式19.2 MVC设计模式详解19.3 MVC与其他Java Web开发模式的区别总结19.4 应用场景总结 在Java Web应用程序开发领域,有效的架构模式和设计模式对提高代码可维护性、模块化以及团队协作至关重要。本文将探讨Java Web开发中的常见模式——模型…...
Z字形变换
问题: 将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下: P A H N A P L S I I G Y I R 之后,你…...

飞书上传图片
飞书上传图片 1. 概述1.1 访问凭证2. 上传图片获取image_key1. 概述 飞书开发文档上传图片: https://open.feishu.cn/document/server-docs/im-v1/image/create 上传图片接口,支持上传 JPEG、PNG、WEBP、GIF、TIFF、BMP、ICO格式图片。 在请求头上需要获取token(访问凭证) …...

Java微服务学习Day1
文章目录 认识微服务服务拆分及远程调用服务拆分服务远程调用提供者与消费者 Eureka注册中心介绍构建EurekaServer注册user-serviceorder-service完成服务拉取 Ribbon负载均衡介绍原理策略饥饿加载 Nacos注册中心介绍配置分级存储负载均衡环境隔离nacos注册中心原理 认识微服务…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...

VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

使用SSE解决获取状态不一致问题
使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件,这个上传文件是整体功能的一部分,文件在上传的过程中…...
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!
【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...
Netty自定义协议解析
目录 自定义协议设计 实现消息解码器 实现消息编码器 自定义消息对象 配置ChannelPipeline Netty提供了强大的编解码器抽象基类,这些基类能够帮助开发者快速实现自定义协议的解析。 自定义协议设计 在实现自定义协议解析之前,需要明确协议的具体格式。例如,一个简单的…...
el-amap-bezier-curve运用及线弧度设置
文章目录 简介示例线弧度属性主要弧度相关属性其他相关样式属性完整示例链接简介 el-amap-bezier-curve 是 Vue-Amap 组件库中的一个组件,用于在 高德地图 上绘制贝塞尔曲线。 基本用法属性path定义曲线的路径,可以是多个弧线段的组合。stroke-weight线条的宽度。stroke…...