蓝桥杯-动态规划-子数组问题

目录

一、乘积最大数组

二、乘积为正数的最长子数组长度

三、等差数列划分

四、最长湍流子数组


心得:

最重要的还是状态表示,我们需要根据题的意思,来分析出不同的题,不同的情况,来分析需要多少个状态

一、乘积最大数组

乘积最大数组

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;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Kubernetes(k8s)之Pod详解

文章目录 Kubernetes之Pod详解一、Pod介绍pod结构pod定义 二、Pod配置pod基本配置镜像拉取策略启动命令环境变量端口设置资源配额 三、Pod生命周期创建和终止初始化容器钩子函数容器探测重启策略 四、Pod调度定向调度NodeNameNodeSelector 亲和性调度NodeAffinityPodAffinityPo…

redis-cluster集群(目的:高可用)

1、特点 集群由多个node节点组成&#xff0c;redis数据分布在这些节点中&#xff0c;在集群中分为主节点和从节点&#xff0c;一个主对应一个从&#xff0c;所有组的主从形成一个集群&#xff0c;每组的数据是独立的&#xff0c;并且集群自带哨兵模式 2、工作原理 集群模式中…

【UGUI】制作用户注册UI界面

这里面主要的操作思想就是 1.打组 同一个事情里面包含两个UI元素都应该打组便于管理和查找 2.设置锚点位置 每次创建一个UI都应该设置他的锚点以便于跟随画布控制自己的&#xff1a;相对位置 3. 设置尺寸&#xff08;像素大小&#xff09; 每一次UI元素哪怕是作为父物体的…

算法的奥秘:常见的六种算法(算法导论笔记2)

算法的奥秘&#xff1a;种类、特性及应用详解&#xff08;算法导论笔记1&#xff09; 上期总结算法的种类和大致介绍&#xff0c;这一期主要讲常见的六种算法详解以及演示。 排序算法&#xff1a; 排序算法是一类用于对一组数据元素进行排序的算法。根据不同的排序方式和时间复…

深入了解 Pinia:现代 Vue 应用的状态管理利器

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…

DMX512协议及对接口电路的分析

1、DMX512协议简介 DMX 是Digital MultipleX 的缩写&#xff0c;意为多路数字传输(具有512条信息的数字多路复用”)。DMX512控制协议是美国舞台灯光协会(usITT)于1990年发布的灯光控制器与灯具设备进行数据传输的工业标准&#xff0c;全称是USITTDMX512(1990); DMX512 在其物理…

Springmvc原理解析

1. DispatcherServlet springmvc的核心控制器&#xff0c;负责截获所有的请求&#xff0c;当截获请求后委托给HandlerMapping进行请求映射的解析工作&#xff0c;目的是找到哪一个Controller的方法可以处理该请求&#xff0c;找到后再交由给HandlerAdaptor去负责调用并返回Mod…

第13周 预习、实验与作业:Java网络编程

目录 1 课前问题列表 1.编写一个网络程序&#xff0c;为了与其他网络程序通信&#xff0c;至少要知道对方的什么信息&#xff1f; 2.TCP与UDP协议有什么不同的呢&#xff1f;什么时候该选择哪种协议&#xff1f;HTTP使用的是TCP还是UDP&#xff1f;不重要的短信息传送之类的功能…

Redis key的类型以及命令

系列文章目录 第一章 Java线程池技术应用 第二章 CountDownLatch和Semaphone的应用 第三章 Spring Cloud 简介 第四章 Spring Cloud Netflix 之 Eureka 第五章 Spring Cloud Netflix 之 Ribbon 第六章 Spring Cloud 之 OpenFeign 第七章 Spring Cloud 之 GateWay 第八章 Sprin…

java基于springboot公益帮学网站 新闻发布系统的设计与实现vue

以Java为开发平台&#xff0c;综合利用Java Web开发技术、数据库技术等&#xff0c;开发出公益帮学网站。用户使用版块&#xff1a;可以选择注册并登录&#xff0c;可以浏览信息、可以网上互动、发布文章、内容推荐等。后台管理员管理版块&#xff1a;以管理员身份登录网站后台…

C语言——打印出所有的“水仙花数”

所谓水仙花数,是指一个3位数,其各位数字立方和等于该数本身。水仙花数是指一个三位数&#xff0c;它的每个位上的数字的立方和等于它本身。例如&#xff0c;153是一个水仙花数&#xff0c;因为1^3 5^3 3^3 153。 #define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>…

VUE语法-$refs和ref属性的使用

1、$refs和ref属性的使用 1、$refs:一个包含 DOM 元素和组件实例的对象&#xff0c;通过模板引用注册。 2、ref实际上获取元素的DOM节点 3、如果需要在Vue中操作DOM我们可以通过ref和$refs这两个来实现 总结:$refs可以获取被ref属性修饰的元素的相关信息。 1.1、$refs和re…

Vue3-pnpm包管理器创建项目

一些优势&#xff1a;比同类工具快2倍左右、节省磁盘空间 官网&#xff1a;pnpm - 速度快、节省磁盘空间的软件包管理器 | pnpm中文文档 | pnpm中文网 npm升级到yarn再升级到pnpm&#xff08;速度更快&#xff09; 安装方式&#xff1a;npm install -g pnpm 创建项目&#…

计算虚拟化之CPU——qemu解析

解析 qemu 的命令行&#xff0c;qemu 的命令行解析&#xff0c;就是下面这样一长串。 qemu_add_opts(&qemu_drive_opts);qemu_add_opts(&qemu_chardev_opts);qemu_add_opts(&qemu_device_opts);qemu_add_opts(&qemu_netdev_opts);qemu_add_opts(&qemu_nic_…

数据结构(超详细讲解!!)第二十五节 树与森林

1.树的存储结构 和线性表一样&#xff0c;树可以用顺序和链式两种存储结构。 树的顺序存储结构适合树中结点比较“满”的情况。根据树的非线性结构特点&#xff0c;常用链式存储方式来表示树。树常用的存储方法有&#xff1a;双亲表示法、孩子表示法和孩子兄弟表…

【Dockerfile】将自己的项目构建成镜像部署运行

目录 1.Dockerfile 2.镜像结构 3.Dockerfile语法 4.构建Java项目 5.基于Java8构建项目 1.Dockerfile 常见的镜像在DockerHub就能找到&#xff0c;但是我们自己写的项目就必须自己构建镜像了。 而要自定义镜像&#xff0c;就必须先了解镜像的结构才行。 2.镜像结构 镜…

蓝桥杯算法双周赛心得——迷宫逃脱(记忆化搜索)

大家好&#xff0c;我是晴天学长&#xff0c;非常经典实用的记忆化搜索题&#xff0c;当然也可以用dp做&#xff0c;我也会发dp的题解&#xff0c;需要的小伙伴可以关注支持一下哦&#xff01;后续会继续更新的。&#x1f4aa;&#x1f4aa;&#x1f4aa; 1) .迷宫逃脱 迷官逃脱…

Mac | Vmware Fusion | 分辨率自动还原问题解决

1. 问题 Mac的Vmware Fusion在使用Windows10虚拟机时&#xff0c;默认显示器配置如下&#xff1a; 开机进入系统并变更默认分辨率后&#xff0c;只要被 ⌘Tab 切换分辨率就会还原到默认&#xff0c;非常影响体验。 2. 解决方式 调整 设置 -> 显示器 -> 虚拟机分辨率…

Authing CEO 谢扬来信 |我的原则

从忙碌的工作中短暂抽身&#xff0c;有很多感想&#xff0c;不吐不快&#xff0c;借此机会&#xff0c;倾我所有&#xff0c;诉我原则。 原则一&#xff1a;坚强信念&#xff0c;坚定意志 商人大多「无利不起早」&#xff0c;而创业者的反馈周期比商人长非常非常多。 相比「商品…

【Linux进阶之路】进程间通信

文章目录 一、原理二、方式1.管道1.1匿名管道1.1.1通信原理1.1.2接口使用 1.2命名管道 2.共享内存2.1原理2.2接口使用 3.消息队列原理 4.信号量引入原理 总结 一、原理 进程间的通信是什么&#xff1f;解释&#xff1a; 简单理解就是&#xff0c;不同进程之间进行数据的输入输出…