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

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 买卖股票的最佳时机

题意理解&#xff1a; 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交…...

SQL语言复习-----1

1&#xff0c;前言 SQL是计算机的一门基础语言&#xff0c;无论在开发还是数据库管理上都是非常重要&#xff0c;最近总结归纳了一下相关知识&#xff0c;记录如下。 2&#xff0c;归纳 SQL是结构化查询语言。 关系数据库有三级模式结构。 基本表和视图一样都是关系。 举例…...

爬虫2—用爬虫爬取壁纸(想爬多少张爬多少张)

先看效果图&#xff1a; 我这个是爬了三页的壁纸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 脚本相关 学习目标 这一节&#xff0c;我们从 基础知识、简单实践、小结 三个方面来学习 基础知识 脚本相关的变量解析 序号变量名解析1$0获取当前执行的shell脚本文件名2$n获取当前执行的shell脚本的第n个参数值&#xff0c;n1…9&#xff0c;当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游戏】系列&#xff01;本系列将引导您一步步学习如何使用Unity开发各种类型的游戏。在这第23篇中&#xff0c;我们将探索如何制作…...

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…...

【深度学习:语义分割】语义分割简介

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

前端开发_AJAX基本使用

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

OnlyOffice-8.0版本深度测评

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

【Go】一、Go语言基本语法与常用方法容器

GO基础 Go语言是由Google于2006年开源的静态语言 1972&#xff1a;&#xff08;C语言&#xff09; — 1983&#xff08;C&#xff09;—1991&#xff08;python&#xff09;—1995&#xff08;java、PHP、js&#xff09;—2005&#xff08;amd双核技术 web端新技术飞速发展&…...

杨中科 ASP.NETCORE 高级14 SignalR

1、什么是websocket、SignalR 服务器向客户端发送数据 1、需求&#xff1a;Web聊天;站内沟通。 2、传统HTTP&#xff1a;只能客户端主动发送请求 3、传统方案&#xff1a;长轮询&#xff08;Long Polling&#xff09;。缺点是&#xff1f;&#xff08;1.客户端发送请求后&…...

哪家洗地机比较好用?性能好的洗地机推荐

在众多功能中&#xff0c;我坚信洗地机的核心依旧是卓越的清洁能力以及易于维护的便捷性&#xff0c;其他的附加功能可以看作是锦上添花&#xff0c;那么如何找到性能好的洗地机呢&#xff1f;我们一起看看哪些洗地机既能确保卫生效果还能使用便利。 洗地机工作原理&#xff1…...

学习与非学习

学习与非学习是人类和动物行为表现中的两种基本形式&#xff0c;它们在认知过程和行为适应上有着根本的区别。理解这两者之间的差异对于把握认知发展、心理学以及教育学等领域的核心概念至关重要。 学习 学习是一个获取新知识、技能、态度或价值观的过程&#xff0c;它导致行为…...

牛客网SQL进阶127: 月总刷题数和日均刷题数

官网链接&#xff1a; 月总刷题数和日均刷题数_牛客题霸_牛客网现有一张题目练习记录表practice_record&#xff0c;示例内容如下&#xff1a;。题目来自【牛客题霸】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应用程序开发领域&#xff0c;有效的架构模式和设计模式对提高代码可维护性、模块化以及团队协作至关重要。本文将探讨Java Web开发中的常见模式——模型…...

Z字形变换

问题&#xff1a; 将一个给定字符串 s 根据给定的行数 numRows &#xff0c;以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时&#xff0c;排列如下&#xff1a; P A H N A P L S I I G Y I R 之后&#xff0c;你…...

飞书上传图片

飞书上传图片 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注册中心原理 认识微服务…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...