蓝桥杯-动态规划-子数组问题
目录
一、乘积最大数组
二、乘积为正数的最长子数组长度
三、等差数列划分
四、最长湍流子数组
心得:
最重要的还是状态表示,我们需要根据题的意思,来分析出不同的题,不同的情况,来分析需要多少个状态
一、乘积最大数组
乘积最大数组

1.状态表示
dp[i]:到达i位置的最大乘积子数组。
2.状态转移方程
dp[i]=Math.max(dp[i-1]*p[i],dp[i-1]);
问题:不能通过简单的最大值来填表,因为他的这个存在负负得正的情况,但是他其实一共乘法分为两种情况
正*正为正 最大值
正*负为负 最小值
负*负为正 最大值
状态表示更改为
f[i]:到达i位置,最大的乘积
g[i]:到达i位置,最小的乘积
所以状态转移方程也需要去变
f[i]=Math.max(nums[i],Math.max(f[i-1]*nums[i],g[i-1]*nums[i]));
g[i]=Math.min(nums[i],Math.min(f[i-1]*nums[i],g[i-1]*nums[i]));3.初始化
f[0]=g[0]=nums[0]
4.填表顺序
从左到右
5.返回值
class Solution {public int maxProduct(int[] nums) {int m=nums.length;//f为最大乘积和//g为最小乘积和int[]f=new int[m];int[]g=new int[m];f[0]=g[0]=nums[0];for(int i=1;i<m;i++){//f[i]状态表示f[i]=Math.max(nums[i],Math.max(f[i-1]*nums[i],g[i-1]*nums[i]));g[i]=Math.min(nums[i],Math.min(f[i-1]*nums[i],g[i-1]*nums[i]));} int ret =-0x3f3f3f3f;for(int i=0;i<m;i++){ret=Math.max(ret,f[i]);}return ret;} }
二、乘积为正数的最长子数组长度

1.状态表示
dp[i]=到达i位置乘积为正数的最长子数组长度
如果要确保乘积是正数,就需要我们上面那个乘积最大的数组的状态表示
f[i]:以i元素为结尾位置,乘积为正数的长度
g[i]:以i位置为结尾位置,乘积为负数的长度
2.状态转移方程
f[i]分为长度为1的情况和长度不为1的情况
长度为一的情况,还要区分是不是为正数
长度不为一的情况,看当前i是正数还是负数
当nums[i]<0的时候我们要想一件事情,假如说g[i-1]正好等于0,然而此时nums[i]<0,那么没有正数,最后的结果不就是等于0吗。所以我们不能写作当nums[i]<0时候,f[i]=g[i-1]+1
3.初始化:
就单纯的看nums[0]大于0还是小于0。 大于0那么f[0]就是1。小于0那么g[0]是1
4.填表顺序:
从左到右
5返回值:返回值最大值
class Solution {public static int getMaxLen(int[] nums) {int m=nums.length;int f[]=new int[m];int g[]=new int[m];if(nums[0]>0){f[0]=1;}else if(nums[0]<0){g[0]=1;}for(int i=1;i<m;i++){//f[i]状态表示if(nums[i]>0){f[i]=f[i-1]+1;if(g[i-1]==0){g[i]=0;}else{g[i]=g[i-1]+1;}}else if(nums[i]<0){if(g[i-1]==0){f[i]=0 ;}else{f[i]=g[i-1]+1;}g[i]=f[i-1]+1;}}int ret=0;for(int i=0;i<m;i++){ret=Math.max(ret,f[i]);}return ret;}}
三、等差数列划分

1.状态表示
dp[i]到达i位置等差数列的个数
2.状态表示
如果nums[i]-nums[i-1]==nums[i-1]-nums[i-2],那么他就构成了一个三个数的等差数组,
如果他之前就是三个数的等差数组,加一个数也就可以组成一个四个数的等差数组
dp[i]=dp[i-1]+1 (多少个数的等差数组)然后假如说由3个变成4个,4-3也就是要加1即可,剩下的那个是在三个里面,换句话说,有上面那个判定条件,它是给你判定三个的,但是假如说你这个是4个,他就不会算在内,所以4个的话就要多加1,五个就要多加一个4个,和一个五个,这样慢慢的规律就是i-2即可(我的意思是假如是五个减去三个)
然后检查三个的是不是一个等差数组
3.初始化:
小于3就是0
4.填表顺序:
从左到右
5.返回值
return dp表中的最大值即可
class Solution {public static int numberOfArithmeticSlices(int[] nums) {int m=nums.length;int[]dp=new int[m];if(m<3){return 0;}int max=0;for(int i=2;i<m;i++){if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){dp[i]=dp[i-1]+1;if(i-2>0&&dp[i-1]!=0){dp[i]=dp[i]+i-2;}max=Math.max(dp[i-1],max);if(i-2>0&&dp[i-1]==0){dp[i]=max+1;}max=Math.max(dp[i],max);}}int ret=0;for(int i=0;i<m;i++){ret=Math.max(dp[i],ret);}return ret;} }
四、最长湍流子数组

湍流数组用图来表示就相当于是
大概就是这种图像的含义。* * * *1.状态表示
dp[i]:到达i位置的最长湍流数组的长度
2.状态表示
if(n%2==0){
假如nums[i]>nums[i+1]}
else{
nums[i]<nums[i+1]}
dp[i]=dp[i-1]+1
在这里我们发现一件事情,一个数组,他最多只能表示当前的一种情况
但这个地方有三个状态,所以不能说单靠一个表达湍流数组的状态
所以我们决定使用f[i],g[i],来表示,前面两种情况,最后那个是0
f[i]:表示在i位置,与i-1位置呈现下降趋势,最长湍流数组长
g[i]:表示在i位置,与i-1位置呈现上升趋势,最长湍流数组长
那么if(nums[i-1]>nums[i]){
f[i]=g[i-1]+1;
g[i]=1;
}
if(nums[i]<nums[i+1]){
f[i]=1;
g[i]=f[i-1]+1;
}
3.初始化
因为假如只有一个数字,那么湍流数组的长度是1,所以说,这个就默认是1了。
从1到n
4.填表顺序
从左到右
5.返回值
返回最大值
class Solution {public int maxTurbulenceSize(int[] arr) {int m=arr.length;int[]f=new int[m];int[]g=new int[m];for(int i=0;i<m;i++){f[i]=g[i]=1;}for(int i=1;i<m;i++){if(arr[i-1]>arr[i]){f[i]=g[i-1]+1;g[i]=1;}if(arr[i-1]<arr[i]){f[i]=1;g[i]=f[i-1]+1;}}int ret=0;for(int i=0;i<m;i++){ret=Math.max(ret,Math.max(g[i],f[i]));}return ret;} }
相关文章:
蓝桥杯-动态规划-子数组问题
目录 一、乘积最大数组 二、乘积为正数的最长子数组长度 三、等差数列划分 四、最长湍流子数组 心得: 最重要的还是状态表示,我们需要根据题的意思,来分析出不同的题,不同的情况,来分析需要多少个状态 一、乘积最…...
CDA一级备考思维导图
CDA一级备考思维导图 第一章 数据分析概述与职业操守1、数据分析概念、方法论、角色2、数据分析师职业道德与行为准则3、大数据立法、安全、隐私 CDA一级复习备考资料共计七个章节,如需资料,请留言,概览如下图: 第一章 数据分析…...
【傻瓜级JS-DLL-WINCC-PLC交互】1.C#用windows窗体控件创建.net控件
思路 JS-DLL-WINCC-PLC之间进行交互,思路,先用Visual Studio创建一个C#的DLL控件,然后这个控件里面嵌入浏览器组件,实现JS与DLL通信,然后DLL放入到WINCC里面的图形编辑器中,实现DLL与WINCC的通信。然后PLC与…...
Unity中Shader的BRDF解析(一)
文章目录 前言现在我们主要来看Standard的 漫反射 和 镜面反射一、PBS的核心计算BRDF二、Standard的镜面高光颜色三、具体的BRDF计算对于BRDF的具体计算,在下篇文章中,继续解析 四、最终代码.cginc文件Shader文件 前言 在上篇文章中,我们解析…...
《软件工程原理与实践》复习总结与习题——软件工程概述
软件 什么是软件? 程序数据配套文档 软件危机 概念 计算机软件的开发和维护过程中所遇到的一系列严重问题 表现 20世纪60年代中后期,大容量、高速度计算机的出现,使计算机应用范围增大,软件开发需求急剧增长 软件工程 背景 德国…...
acwing算法基础之动态规划--线性DP和区间DP
目录 1 基础知识2 模板3 工程化 1 基础知识 线性DP:状态转移表达式存在明显的线性关系。 区间DP:与顺序有关,状态与区间有关。 2 模板 3 工程化 题目1:数字三角形。 解题思路:直接DP即可,f[i][j]可以来…...
力扣 622.设计循环队列
目录 1.解题思路2.代码实现 1.解题思路 首先,该题是设计循环队列,因此我们有两种实现方法,即数组和链表,但具体考虑后,发现数组实现要更容易一些,因此使用数组实现,因此我们要给出头和尾变量&a…...
初识Linux(2).妈妈再也不用担心我Linux找不到门了。
文章目录 前言 1.man指令(重要):例如: 2.cp指令(重要):例如:把123.txt复制到a目录中类似window如下操作: 3.mv例如:类似window如下操作: 4.nano例…...
房屋租赁出售经纪人入驻小程序平台
一款专为房屋中介开发的小程序平台,支持独立部署,源码交付,数据安全无忧。 核心功能:房屋出租、经纪人独立后台、分佣后台、楼盘展示、房型展示、在线咨询、地址位置配套设施展示。 程序已被很多房屋交易中介体验使用过&#x…...
【计算方法与科学建模】矩阵特征值与特征向量的计算(五):乘幂法的加速(带有原点移位的乘幂法)
文章目录 一、Jacobi 旋转法二、Jacobi 过关法三、Householder 方法四、乘幂法四、乘幂法的加速 矩阵的特征值(eigenvalue)和特征向量(eigenvector)在很多应用中都具有重要的数学和物理意义。 本文将详细介绍乘幂法的基本原理和步…...
2023年【起重机械指挥】考试题库及起重机械指挥考试资料
题库来源:安全生产模拟考试一点通公众号小程序 2023年【起重机械指挥】考试题库及起重机械指挥考试资料,包含起重机械指挥考试题库答案和解析及起重机械指挥考试资料练习。安全生产模拟考试一点通结合国家起重机械指挥考试最新大纲及起重机械指挥考试真…...
GoLang语言范围(Range)
目录 一、在数组、切片上使用‘range’ 二、在映射上使用range 三、在通道上使用range Go语言中的range关键字用于迭代数组(数组、切片、字符串)、映射(map)、通道(channel)或者在 for 循环中迭代每一个…...
汽车电子 -- 车载ADAS之FCW(前方碰撞预警)
相关法规文件: FCW: GB∕T 33577-2017 智能运输系统 车辆前向碰撞预警系统 性能要求和测试规程 一、前方碰撞预警 FCW( Forward Collision Warning) 参看:法规标准-GB/T 33577标准解读(2017版) 1、状态机 系统关闭 当车辆前向碰撞预警系…...
爬虫系统Docker和Kubernetes部署运维最佳实践
在构建和管理爬虫系统时,使用Docker和Kubernetes可以带来诸多好处,如方便的部署、弹性伸缩和高可靠性。然而,正确的部署和运维实践对于确保系统稳定运行至关重要。在本文中,我将分享爬虫系统在Docker和Kubernetes上的最佳部署和运…...
音视频5、libavformat-1
libavformat库,是FFmpeg中用于处理各种媒体容器格式(media container format)的库。它的两个最主要的功能是 : demuxing:解封装,将一个媒体文件分割为多个多媒体流 muxing:封装,将多个多媒体数据流写入到指定媒体容器格式的文件中 这两个过程所做的…...
【数据结构复习之路】树和二叉树(严蔚敏版)万字详解主打基础
专栏:数据结构复习之路 复习完上面四章【线性表】【栈和队列】【串】【数组和广义表】,我们接着复习 树和二叉树,这篇文章我写的非常详细且通俗易懂,看完保证会带给你不一样的收获。如果对你有帮助,看在我这么辛苦整理…...
nginx使用详解:转发规则、负载均衡、server_name
文章目录 一、nginx常用的转发规则location 指令说明location转发使用 二、upstream负载均衡使用三、server_name使用四、其他常用配置限制请求类型处理静态资源目录遍历问题限制客户端使用的ip或者域名 五、需要注意的地方location /api1 探讨location ~ /api1 探讨࿰…...
HarmonyOS 数据持久化 Preferences 如何在页面中对数据进行读写
背景介绍 最近在了解并跟着官方文档尝试做一个鸿蒙app 小demo的过程中对在app中保存数据遇到些问题 特此记录下来 这里的数据持久化以 Preferences为例子展开 废话不多说 这里直接上节目(官方提供的文档示例:) 以Stage模型为例 1.明确preferences的类型 import data_prefer…...
ESP32-Web-Server编程- JS 基础 4
ESP32-Web-Server编程- JS 基础 4 概述 HTML 内联事件处理器,你永远不应该使用 HTML 事件处理器属性——因为那些已经过时了,使用它们是不好的做法。 在前端编程中,除了将期望发生的事件写为 JS 文件外,还可以使用一些组件自带…...
JAVA的反射机制
什么是反射机制 Java反射机制是指在运行时动态地获取类的信息并操作类的成员(属性、方法、构造方法等)的能力。通过反射,我们可以解析出类的完整信息,包括构造函数、成员变量、继承关系等。以下是一个使用反射机制创建对象、调用…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...


