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

这篇具有很好参考价值的文章主要介绍了蓝桥杯-动态规划-子数组问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、乘积最大数组

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

三、等差数列划分

四、最长湍流子数组


心得:

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

一、乘积最大数组

乘积最大数组

蓝桥杯-动态规划-子数组问题,蓝桥杯,动态规划,职场和发展

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.返回值

返回最大值文章来源地址https://www.toymoban.com/news/detail-754353.html

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

到了这里,关于蓝桥杯-动态规划-子数组问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯备赛之动态规划篇——涂色问题(区间DP)

    2023第十四届蓝桥杯模拟赛第二期个人题解(Java实现) 2023第十四届蓝桥杯模拟赛第三期个人题解(Java实现) 蓝桥杯备赛之动态规划篇——背包问题 蓝桥杯真题——单词分析(Java实现) 😘😘 哈喽,大家好!这里是蓝桥杯系列文章的动态规划章节🔥🔥,今天要讲解的是区

    2024年01月23日
    浏览(49)
  • 【动态规划】两个数组问题

    题目链接 状态表示 dp[i][j] 表示 s1 0 到 i 区间内,以及时s2 0 到 j 区间内所有的子序列中,最长的公共子序列 状态转移方程 根据最后一个位置的请款分类讨论。 初始化 关于字符串的dp问题,空串是有研究意义的。引入空串的概念之后会方便我们的初始化 这里还可以使用之前

    2024年02月11日
    浏览(35)
  • c++ 子数组动态规划问题

    1.最大子数组和   力扣 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 示例 1: 示例 2: 示例 3: 2.环形子数组最大和 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给

    2024年02月12日
    浏览(38)
  • 动态规划——数塔问题(三维数组的应用)

    声明:理论指导《算法设计与分析 第四版》 因为这个地方用到了三维数组,感觉很有意思就故意挑出来分享给大家(三维数组可以看成很多页二维数组) 4.5.1认识动态规划 数塔问题: 如图4-12所示的一个数塔,从顶层到底层或从底层到顶层,在每一结点可以选择向左走或是

    2024年02月03日
    浏览(35)
  • 两个数组的dp问题(2)--动态规划

      一)交错字符串: 97. 交错字符串 - 力扣(LeetCode) 一)确定一个状态标识: 如果我选择s1的一段区间,再进行选择s2得一段区间,那么s3这个字符串的长度就已经固定 预处理:在s1字符串s2字符串和s3字符串前面加上一个虚拟字符,让下标从1开始进行计数 如果要是从1号位置开始进

    2024年02月15日
    浏览(41)
  • 从二维数组到一维数组——探索01背包问题的动态规划优化

    本文将继续上一篇博客爬楼梯之后继续讲解同样用到了动态规划的 01背包问题 在解决动态规划问题时,我们经常面临着空间复杂度的挑战。01背包问题是一个典型的例子,通常使用二维数组来表示状态转移,但这样会带来额外的空间开销。在本文中,我们将探讨如何通过优化

    2024年04月11日
    浏览(60)
  • 动态规划:两个数组的dp问题(C++)

    动态规划往期文章: 动态规划入门:斐波那契数列模型以及多状态 动态规划:路径和子数组问题 动态规划:子序列问题 动态规划:回文串问题 1.最长公共子序列(中等) 链接 :最长公共子序列 题目描述 做题步骤 状态表示 对于两个数组的dp,采用一维dp是没有办法清晰的表

    2024年02月08日
    浏览(50)
  • 动态规划:路径和子数组问题(C++)

    1.不同路径(中等) 链接:不同路径 题目描述 做题步骤 状态表示 尝试 定义状态表示为到达[m, n]位置的路径数 。 状态转移方程 通过上述分析,可知状态转移方程为: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 。 初始化 填表顺序 保证填当前状态时,所需状态已经计算过,从起点出发,

    2024年02月10日
    浏览(30)
  • 【动态规划】01背包问题(滚动数组 + 手画图解)

            01背包除了可以用形象的二维动态数组表示外,还可以使用空间复杂度更低的一维滚动数组。 目录 文章目录 前言 一、滚动数组的基本理解 二、确定dp及其下标含义 三、确定递推公式 四、确定初始化 五、确定遍历顺序 1.用物品(正序)遍历背包(正序) 实现代码:

    2023年04月08日
    浏览(35)
  • 算法沉淀——动态规划篇(子数组系列问题(下))

    几乎所有的动态规划问题大致可分为以下5个步骤,后续所有问题分析都将基于此 1.、状态表示:通常状态表示分为以下两种,其中更是第一种为主。 以i为结尾 ,dp[i] 表示什么,通常为代求问题(具体依题目而定) 以i为开始 ,dp[i]表示什么,通常为代求问题(具体依题目而

    2024年04月14日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包