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

目录

一、乘积最大数组

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

三、等差数列划分

四、最长湍流子数组


心得:

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

一、乘积最大数组

乘积最大数组

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

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

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

相关文章

7.前端--CSS-字体属性【2023.11.26】

CSS字体属性 CSS Fonts (字体)属性用于定义字体样式、粗细、大小、和字形。 1.文字样式 CSS 使用 font-style 属性设置文本的风格。 语法&#xff1a; p { font-style: normal; }属性&#xff1a; 2字体粗细 CSS 使用 font-weight 属性设置文本字体的粗细。 语法&#xff1a…

Deep Learning(wu--46)

文章目录 ContentsBeginBasic逻辑回归SGD导数计算图&#xff08;反向传播&#xff09;向量化广播numpy Neural Network向量化激活函数梯度下降深层表示反向传播 Contents Begin Basic 逻辑回归 SGD 导数 计算图&#xff08;反向传播&#xff09; 向量化 广播 numpy Neural Netw…

嵌入式八股 | 笔试面试 | 校招秋招 | 题目精选

嵌入式八股精华版1.0所有216道题目如下&#xff1a; 欢迎关注微信公众号【赛博二哈】并加入嵌入式求职交流群。提供简历模板、学习路线、岗位整理等 欢迎加入知识星球【嵌入式求职星球】获取完整嵌入式八股。 提供简历修改、项目推荐、求职规划答疑。另有各城市、公…

Grafana采用Nginx反向代理

一、场景介绍 在常规操作中&#xff0c;一般情况下不会放开许多端口给外部访问&#xff0c;特别是直接 ip:port 的方式开放访问。但是 Grafana 的请求方式在默认情况下是没有任何规律可寻的。 为了满足业务需求&#xff08;后续通过 Nginx 统一一个接口暴露 N 个服务&#xf…

基于Java SSM框架+Vue留学生交流互动论坛网站项目【项目源码+论文说明】计算机毕业设计

基于java的SSM框架Vue实现学生交流互动论坛网站演示 摘要 21世纪的今天&#xff0c;随着社会的不断发展与进步&#xff0c;人们对于信息科学化的认识&#xff0c;已由低层次向高层次发展&#xff0c;由原来的感性认识向理性认识提高&#xff0c;管理工作的重要性已逐渐被人们所…

【开源】基于Vue和SpringBoot的个人健康管理系统

项目编号&#xff1a; S 040 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S040&#xff0c;文末获取源码。} 项目编号&#xff1a;S040&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 健康档案模块2.2 体检档案模块2.3 健…

python爬取招聘网站信息

废话不多说&#xff0c;直接上代码&#xff0c;开箱即用。该文件抓取的是智联招聘网站的招聘信息&#xff0c;可以根据需要设置输入搜索关键词和查找页数&#xff0c;就会得到结果&#xff0c;可以搜索到每个岗位的岗位名称、公司名称、学历要求、公司规模、福利待遇、行业、薪…

【Web】PHP反序列化刷题记录

目录 ①[NISACTF 2022]babyserialize ②[NISACTF 2022]popchains ③[SWPUCTF 2022 新生赛]ez_ez_unserialize ④[GDOUCTF 2023]反方向的钟 再巩固下基础 ①[NISACTF 2022]babyserialize <?php include "waf.php"; class NISA{public $fun"show_me_fla…

【腾讯云云上实验室】用向量数据库在金融信用数据库分析中的实战运用

一、前言 这篇文章将带领读者探索数据库的多样化解决方案及其演进历程&#xff0c;特别关注向量数据库的重要性和在实际项目中的应用。 通过深入剖析腾讯云向量数据库及其在金融信用数据库分析中的实战运用&#xff0c;为读者提供全面而实用的指南&#xff0c;帮助他们理解、…

Node——Node.js简介

Node.js是一个基于Chrome V8引擎的JavaScript运行时环境&#xff0c;它能够让JavaScript脚本运行在服务端&#xff0c;这使得JavaScript成为与PHP、Python等服务端语言平起平坐的脚本语言。 1、认识Node.js Node.js是当今网站开发中非常流行的一种技术&#xff0c;它以简单易…

什么是 dropblock

大家好啊&#xff0c;我是董董灿。 之前介绍过 dropout 算法&#xff0c;它在训练神经网络中&#xff0c;可以随机丢弃神经元&#xff0c;是一种防止网络过拟合的方法。 但是在卷积神经网络中&#xff0c;dropout 的表现却不是很好&#xff0c;于是研究人员又搞了一个“结构化…

Drool 7 SpreadSheet Decision Template 笔记

1 Excel Decision table 1.1 很棒的示意图&#xff0c;来自https://blog.csdn.net/justlpf/article/details/128109731 1.2 参考URL 1.2.1 https://blog.csdn.net/justlpf/article/details/128109731 1.3 多sheet 模式 默认是用第一个sheet如果要支持多sheet&#xff0c;需…

Java核心知识点整理大全17-笔记

Java核心知识点整理大全-笔记_希斯奎的博客-CSDN博客 Java核心知识点整理大全2-笔记_希斯奎的博客-CSDN博客 Java核心知识点整理大全3-笔记_希斯奎的博客-CSDN博客 Java核心知识点整理大全4-笔记-CSDN博客 Java核心知识点整理大全5-笔记-CSDN博客 Java核心知识点整理大全6…

基于SpringBoot+Vue的蛋糕商城【源码好优多】

简介 蛋糕商城首页、注册、登录、浏览商品、购物车、下单、收藏商品、个人中心、管理员登录、角色管理、日志管理、菜单管理、轮播图管理、商品类别管理、商品管理、用户管理、订单管理、收货地址管理等功能模块。 项目目录 数据库 首页 用户注册 登录 商品详情 个人信息 购物车…

Pytorch项目的文件结构一般都是怎么组织的?

如果是从一些比较典型的论文里弄下来的源码&#xff0c;你会发现它们的论文结构往往都非常复杂。不同的模型、不同的论文&#xff0c;可能代码结构组织的方式都不一样。但它们都不外乎就是经历这几个方面&#xff1a; 1、模型和结构模块定义&#xff1b; 2、数据集获取与处理…

从源码重新真正认识RateLimiter(SmoothBursty实现)

前言 相信大家对于谷歌RateLimiter一定并不陌生,在项目中应该也经常拿来进行限流&#xff0c;但是对于其实现原理并不一定能用熟于心&#xff0c;本文带大家从源码探究RateLimiter的设计与具体实现。 RateLimiter的组成 从源码可以看到&#xff0c;RateLimiter由stopwatch与m…

Codeforces Round 911 (Div. 2)(C~E)(DFS、数论(容斥)、SCC缩点 + DAG图上DP)

​​​​​​1900C - Anjis Binary Tree 题意&#xff1a; 凯克西奇一直被安吉冷落。通过一个共同的朋友&#xff0c;他发现安吉非常喜欢二叉树&#xff0c;于是决定解决她的问题&#xff0c;以引起她的注意。Anji 给了 Keksic 一棵有 n个顶点的二叉树。顶点 1 是根&#xff…

[Spring] 字节一面~Spring 如何解决循环依赖问题 以及 @resource 与 @autowire 同时存在时谁生效

文章目录 Spring 如何解决循环依赖问题resource 与 autowire 同时存在时谁生效 Spring 如何解决循环依赖问题 Spring在实例化一个bean的时候&#xff0c;是首先递归实例化其所依赖的所有bean&#xff0c;直到某个bean没有依赖其他bean&#xff0c;此时就会将该实例返回&#x…

基于Java SSM框架+Vue实现大学生兼职信息网站项目【项目源码+论文说明】

基于java的SSM框架Vue实现大学生兼职信息网站演示 摘要 21世纪的今天&#xff0c;随着社会的不断发展与进步&#xff0c;人们对于信息科学化的认识&#xff0c;已由低层次向高层次发展&#xff0c;由原来的感性认识向理性认识提高&#xff0c;管理工作的重要性已逐渐被人们所认…

【GD32307E-START】开发板开箱、开发环境建立及工程模板测试

01-GD32F307E-START开箱、开发环境建立及工程模板测试&#xff08;Keil-MDK GCC Template&#xff09; 兆易GD32307E-START开发板搭载GD32 ARM Cortex-M4微控制器主流芯片GD32F307。 开箱 板子的做工还是非常精良小巧的。有两颗按键&#xff0c;一颗是复位&#xff0c;一颗是…