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

手撕算法-买卖股票的最佳时机 II(买卖多次)

描述

image.png

分析

使用动态规划。
dp[i][0] 代表 第i天没有股票的最大利润
dp[i][1] 代表 第i天持有股票的最大利润

状态转移方程为:
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]); // 前一天没有股票,和前一天有股票今天卖掉的最大值
dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]); // 前一天没有股票今天买,和前一天也有股票的最大值

初始状态:
dp[0][0] = 0; // 第一天不持有股票
dp[0][1] = prices[0]; // 第一天持有股票,需要减去第一天的股票价格

返回值:
dp[n - 1][0];// 最后一天必须卖掉股票

代码

根据初始状态和状态转移方程写出代码

class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n][2];dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < n; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 前一天没有股票,和前一天有股票今天卖掉的最大值dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]); // 前一天没有股票今天买,和前一天也有股票的最大值}return dp[n - 1][0];// 最后一天必须卖掉股票}
}

面试公司

相关文章:

手撕算法-买卖股票的最佳时机 II(买卖多次)

描述 分析 使用动态规划。dp[i][0] 代表 第i天没有股票的最大利润dp[i][1] 代表 第i天持有股票的最大利润 状态转移方程为&#xff1a;dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]); // 前一天没有股票&#xff0c;和前一天有股票今天卖掉的最大值dp[i][1] max(dp[i-1…...

技术创新与产业升级

在政府工作报告中,新兴技术如云计算、大数据、人工智能等被多次提及,这反映了政府高度重视新一代信息技术在推动经济社会发展中的重要作用。对于计算机行业而言,抓住这些新兴技术的发展机遇,推动技术创新和产业升级,将是未来发展的关键所在。 云计算作为一种新兴的计算模式,正…...

透视未来工厂:山海鲸可视化打造数字孪生新篇章

在信息化浪潮的推动下&#xff0c;数字孪生工厂项目正成为工业制造领域的新宠。作为一名山海鲸可视化的资深用户&#xff0c;我深感其强大的数据可视化能力和数字孪生技术在工厂管理中的应用价值&#xff0c;同时我们公司之前也和山海鲸可视化合作制作了一个智慧工厂项目&#…...

三.寄存器(内存访问)

1.内存中字的存储 2.并不是所有cpu都支持将数据段送入段寄存器&#xff0c;所以有时候用个别的寄存器先把数据段存储起来&#xff0c;再把该寄存器mov到段寄存器。 3.字的传送 4.栈 5.栈机制 举例说明 6.栈顶超界问题 push超界 pop超界 7.栈段...

Day31 贪心算法

Day31 贪心算法 455.分发饼干 我的思路&#xff1a; 小孩数组g指针一直前移&#xff0c;只有饼干数组s满足条件时&#xff0c;才前移&#xff0c;并且更新num 解答&#xff1a; class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.…...

【WEEK4】 【DAY5】AJAX - Part Two【English Version】

2024.3.22 Friday Following the previous article 【WEEK4】 【DAY4】AJAX - Part One【English Version】 Contents 8.4. Ajax Asynchronous Data Loading8.4.1. Create User.java8.4.2. Add lombok and jackson support in pom.xml8.4.3. Change Tomcat Settings8.4.4. Mo…...

力扣100热题[哈希]:最长连续序列

原题&#xff1a;128. 最长连续序列 题解&#xff1a; 官方题解&#xff1a;. - 力扣&#xff08;LeetCode&#xff09;题解&#xff0c;最长连续序列 &#xff1a;哈希表 官方解题思路是先去重&#xff0c;然后判断模板长度的数值是否存在&#xff0c;存在就刷新&#xff0c…...

python笔记基础--文件和存储数据(7)

目录 1.从文件中读取数据 2.写入文件 3.存储数据 3.1使用json.dump()和json.load() 3.2保存和读取用户生成的数据 3.3重构 1.从文件中读取数据 读取整个文件 with open(data.txt) as file_object: contents file_object.read()print(contents)print(contents.rstrip…...

Vue黑马笔记(最新)

VUE vue是一个用于构建用户界面的渐进式框架 创建一个VUE实例 核心步骤&#xff1a; 准备容器引包&#xff08;官网&#xff09;-开发版本/生产版本创建一个vue实例 new vue()指定配置项->渲染数据 el指定挂载点&#xff08;选择器&#xff09;,指定管理的是哪个容器。dat…...

安全工具介绍 SCNR/Arachni

关于SCNR 原来叫Arachni 是开源的&#xff0c;现在是SCNR&#xff0c;商用工具了 可试用一个月 Arachni Web Application Security Scanner Framework 看名字就知道了&#xff0c;针对web app 的安全工具&#xff0c;DASTIAST吧 安装 安装之前先 sudo apt-get update sudo…...

赋能数据收集:从机票网站提取特价优惠的JavaScript技巧

背景介绍 在这个信息时代&#xff0c;数据的收集和分析对于旅游行业至关重要。在竞争激烈的市场中&#xff0c;实时获取最新的机票特价信息能够为旅行者和旅游企业带来巨大的优势。 随着机票价格的频繁波动&#xff0c;以及航空公司和旅行网站不断推出的限时特价优惠&#xff…...

【大模型】在VS Code(Visual Studio Code)上安装中文汉化版插件

文章目录 一、下载安装二、配置显示语言&#xff08;一&#xff09;调出即将输入命令的搜索模式&#xff08;二&#xff09;在大于号后面输入&#xff1a;Configure Display Language&#xff08;三&#xff09;重启 三、总结 【运行系统】win 11 【本文解决的问题】 1、英文不…...

自定义WordPress顶部的菜单的方法

要自定义WordPress顶部的菜单&#xff0c;你需要使用WordPress的菜单系统。首先&#xff0c;你需要创建自定义菜单&#xff0c;然后将其设置为顶部导航菜单。 以下是创建自定义菜单并设置其为顶部导航菜单的步骤&#xff1a; 登录到WordPress管理界面。转到“外观”>“菜单…...

独孤思维:流量暴涨,却惨遭违规

最近独孤操作虚拟资料短视频&#xff0c;有个很深的感悟。 每天发10条短视频&#xff0c;积累到20天左右&#xff0c;播放量和粉丝数开始暴涨。 虽然很多牛比的比我数据好&#xff0c;但是对于刚做短视频的独孤来说&#xff0c;我已经满足了。 但是又发了10来天&#xff0c;…...

【python 装饰器 - 重试】做一个简易重试装饰器,如果函数执行错误则会自动重新执行,可设置重试次数,对爬虫比较友好

文章日期&#xff1a;2024.03.19 使用工具&#xff1a;Python 类型&#xff1a;装饰器 文章全程已做去敏处理&#xff01;&#xff01;&#xff01; 【需要做的可联系我】 AES解密处理&#xff08;直接解密即可&#xff09;&#xff08;crypto-js.js 标准算法&#xff09;&…...

Linux线程补充之——同步

一、Linux线程同步 ​ 同步是相对于竞争的概念&#xff1b; ​ 同步就是在保证安全的前提下啊&#xff0c;按照一定的顺序访问临界资源&#xff1b; ​ 所有的资源一定是先访问的临界资源&#xff0c;申请失败然后才进行排队的&#xff1b;互斥锁保证的是来访问的进程只允许…...

面试九 设计模式

单例模式通常被归类为创建型设计模式&#xff0c;因为它主要关注如何创建对象的实例&#xff0c;以及如何确保在整个应用程序生命周期中只有一个实例存在。 1.为什么日志模块和数据库连接池需要单例模式 使用单例模式来实现数据库连接池主要有以下几个原因&#xff1a; 全局唯…...

c++和c语言的区别实例

C和C语言在程序设计领域内具有深远的影响&#xff0c;它们不仅丰富了编程的世界&#xff0c;也为软件开发人员提供了强大的工具。虽然C是在C语言的基础上发展起来的&#xff0c;但两者之间存在着一些关键的区别。为了更深入地理解这些不同&#xff0c;本文将从多个维度探讨C和C…...

图论基础|841.钥匙和房间、463. 岛屿的周长

目录 841.钥匙和房间 思路&#xff1a;本题是一个有向图搜索全路径的问题。 只能用深搜&#xff08;DFS&#xff09;或者广搜&#xff08;BFS&#xff09;来搜。 463. 岛屿的周长 841.钥匙和房间 力扣题目链接 (opens new window) 有 N 个房间&#xff0c;开始时你位于 0…...

把 Taro 项目作为一个完整分包,Taro项目里分包的样式丢失

现象&#xff1a; 当我们把 Taro 项目作为原生微信小程序一个完整分包时&#xff0c;Taro项目里分包的样式丢失&#xff0c;示意图如下&#xff1a; 原因&#xff1a; 在node_modules/tarojs/plugin-indie/dist/index.js文件里&#xff0c;限制了只有pages目录下会被引入app.w…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

游戏开发中常见的战斗数值英文缩写对照表

游戏开发中常见的战斗数值英文缩写对照表 基础属性&#xff08;Basic Attributes&#xff09; 缩写英文全称中文释义常见使用场景HPHit Points / Health Points生命值角色生存状态MPMana Points / Magic Points魔法值技能释放资源SPStamina Points体力值动作消耗资源APAction…...

基于 HTTP 的单向流式通信协议SSE详解

SSE&#xff08;Server-Sent Events&#xff09;详解 &#x1f9e0; 什么是 SSE&#xff1f; SSE&#xff08;Server-Sent Events&#xff09; 是 HTML5 标准中定义的一种通信机制&#xff0c;它允许服务器主动将事件推送给客户端&#xff08;浏览器&#xff09;。与传统的 H…...

学习 Hooks【Plan - June - Week 2】

一、React API React 提供了丰富的核心 API&#xff0c;用于创建组件、管理状态、处理副作用、优化性能等。本文档总结 React 常用的 API 方法和组件。 1. React 核心 API React.createElement(type, props, …children) 用于创建 React 元素&#xff0c;JSX 会被编译成该函数…...

[10-1]I2C通信协议 江协科技学习笔记(17个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17...