手撕算法-买卖股票的最佳时机 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];// 最后一天必须卖掉股票
    }
}

面试公司

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/481539.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

智能财务新选择!Zoho Books入选福布斯榜单,助力中小企业!

放眼全球&#xff0c;中小企业始终是经济发展的重要组成部分。然而&#xff0c;由于中小企业的规模、流程规范和资源等方面受限较多&#xff0c;从而导致其在管理及运营上存在着诸多问题。其中包括财务管理不规范、成本控制不到位、运营效率低下等&#xff0c;这些问题则直接影…

如何在CentOS安装SQL Server数据库并实现无公网IP远程连接内网数据库

文章目录 前言1. 安装sql server2. 局域网测试连接3. 安装cpolar内网穿透4. 将sqlserver映射到公网5. 公网远程连接6.固定连接公网地址7.使用固定公网地址连接 前言 简单几步实现在Linux centos环境下安装部署sql server数据库&#xff0c;并结合cpolar内网穿透工具&#xff0…

基于GD32E230C8T6的数字示波器

基于GD32E230C8T6的数字示波器 文章目录 基于GD32E230C8T6的数字示波器基于GD32E230C8T6的数字示波器实物演示电路原理**模拟前端处理电路**image.png**交直流耦合电路****输入信号衰减电路****信号调理电路****虚断:****虚短:****电压跟随器****反相比例放大器****同相比例放…

深度剖析GNSS高精度定位原理

一、背景 目前室外使用最广泛的定位手段是GNSS定位&#xff0c;常规的GNSS定位精度约5、10米左右&#xff0c;无法满足高精度场景的应用&#xff0c;如何提升GNSS定位性能是亟待解决的问题。本文由浅入深剖析GNSS定位原理并介绍如何实现厘米级高度定位。 二、GNSS定位原理 1、…

MySQL下载安装和本地连接

1、下载MySQL 从MySQL官网下载MySQL Community Server版本&#xff1a; 下载地址&#xff1a;MySQL官网 1、进入官网&#xff0c;点击DOWNLOADS 2、点击MySQL Community(GPL)Downloads 3、点击MySQL Installer for Windows 4、这个会直接跳转到最新的版本 如果想下载以往的…

面试算法-83-不同路径 II

题目 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish”&#xff09;。 现在考虑网格中有障碍物。那么从左上角到…

【进程概念】启动进程 | 查看进程 | 创建进程

目录 启动进程 查看进程 方法1&#xff1a;/proc 方法2&#xff1a;查看脚本 ​方法3&#xff1a;系统调用获取进程标示符❗❗ 终止进程 创建进程&#xff08;主fork) &#x1f642;查看父子进程的pid &#x1f642;进程创建/执行/终止 &#x1f642;多次重新启动进…

java的IO之NIO

NIO是一种同步非阻塞的I/O模型&#xff0c;在Java 1.4中引入了NIO框架&#xff0c;对应java.nio包&#xff0c;提供了channel、selector、buffer等。 NIO中的N可以理解为Non-blocking不在单纯是New&#xff0c;它支持面向缓冲的&#xff0c;基于通道的I/O操作方法。NIO提供了与…

论文阅读之LORA: LOW-RANK ADAPTATION OF LARGE LAN- GUAGE MODELS(2021)

文章目录 论文地址主要内容主要贡献模型图技术细节实验结果 论文地址 LORA: LOW-RANK ADAPTATION OF LARGE LAN- GUAGE MODELS 主要内容 这篇文章的主要内容是介绍了一种名为LoRA&#xff08;Low-Rank Adaptation&#xff09;的技术&#xff0c;这是一种针对大型语言模型进行…

阅读MySQL知识4

一、MySQL数据库主从同步延迟产生的原因 MySQL的主从复制都是单线程的操作&#xff0c;主库对所有DDL和DML产生的日志写进binlog&#xff0c;由于binlog是顺序写&#xff0c;所以效率很高。 Slave的SQL Thread线程将主库的DDL和DML操作事件在slave中重放。DML和DDL的IO操作…

【欧拉函数+快速幂】第十四届蓝桥杯省赛C++ C组 Java A组/研究生组 Python 研究生组《互质数的个数》(C++)

【题目描述】 给定 a,b&#xff0c;求 1≤x< 中有多少个 x 与 互质。 由于答案可能很大&#xff0c;你只需要输出答案对 998244353 取模的结果。 【输入格式】 输入一行包含两个整数分别表示 a,b&#xff0c;用一个空格分隔。 【输出格式】 输出一行包含一个整数表示…

8-深度学习

声明 本文章基于哔哩哔哩付费课程《小白也能听懂的人工智能原理》。仅供学习记录、分享&#xff0c;严禁他用&#xff01;&#xff01;如有侵权&#xff0c;请联系删除 目录 一、知识引入 &#xff08;一&#xff09;深度学习 &#xff08;二&#xff09;Tensorflo…

Java全栈课程之Linux———基本属性

一、看懂文件属性 Linux系统是一种典型的多用户系统&#xff0c;不同的用户处于不同的地位&#xff0c;拥有不同的权限。为了保护系统的安全性&#xff0c;Linux系统对不同的用户访问同一文件&#xff08;包括目录文件&#xff09;的权限做了不同的规定。 在Linux中我们可以使…

深入理解Ubuntu22:探索Linux操作系统的功能与应用

一、linux &#xff08;一&#xff09;、安装 1、电脑可以安装双系统&#xff0c;即在一套硬件上只能同时运行一个操作系统&#xff0c;例&#xff1a;C盘安装win&#xff0c;D盘安装linux。 2、虚拟机 虚拟机需要硬件支持&#xff0c;并需开启VT-x. 如&#xff1a;Virtual…

Ubuntu18.04显示--有线连接未托管

引用: Ubuntu18.04连不网 报"有线连接未托管"_ubuntu20.04以太网未托管-CSDN博客 正文 虚拟机环境配置&#xff1a; VirtaualBox Ubuntu18.04桌面版 问题现象&#xff1a; Ubuntu18.04虚拟机的桌面上提示“有线连接未托管”&#xff0c;虚拟机不能上网&#xf…

使用倒模耳机壳UV树脂胶液制作舞台监听耳返入耳式耳机壳有哪些缺点?

使用倒模耳机壳UV树脂胶液制作舞台监听耳返入耳式耳机壳也存在一些缺点&#xff0c;具体如下&#xff1a; 成本较高&#xff1a;相对于传统的塑料或金属材料&#xff0c;UV树脂胶液的成本较高&#xff0c;需要更多的材料和工艺成本。制作难度较大&#xff1a;由于UV树脂的特殊…

鸿蒙ArkTS实战开发-Native XComponent组件的使用

介绍 本篇Codelab主要介绍如何使用XComponent组件调用NAPI来创建EGL/GLES环境&#xff0c;实现在主页面绘制一个正方形&#xff0c;并可以改变正方形的颜色。本篇CodeLab使用Native C模板创建。 如图所示&#xff0c;点击绘制矩形按钮&#xff0c;XComponent组件绘制区域中渲…

校招岗位大解析

校园招聘岗位需要综合考虑岗位描述、行业背景、公司文化、职业发展路径、技能要求、薪酬福利以及公司口碑等多个方面的因素&#xff0c;全面了解并综合考虑这些因素&#xff0c;才能更好地选择适合自己的岗位&#xff0c;实现个人职业发展目标。 1. 软件/后端/前端开发 软件/…

【SpringBoot】如何定义接口

定义get接口 使用GetMapping定义一个基本get接口 RestController //表示定义一个json格式返回给前端 public class test {private Map<String,Object> map new HashMap<>();GetMapping(value "/test") //定义接口路径public Object userInfo(Strin…

搭建Linux内核开发环境——保姆教程(持续更新中)

搭建Linux内核开发环境——保姆教程&#xff08;持续更新中&#xff09; git版本管理汇编器链接器调试器编辑器构建系统模拟器文档工具图形设计工具 在此文中&#xff0c;持续完善&#xff0c;搭建内核开发环境的细节&#xff0c;有需要的小伙伴儿可以持续关注下 git版本管理 …