首页 > 其他分享 >代码随想录 day56 最长递增子序列 最长连续递增序列 最长重复子数组

代码随想录 day56 最长递增子序列 最长连续递增序列 最长重复子数组

时间:2024-02-20 22:24:45浏览次数:20  
标签:结尾 递增 序列 长度 最长 dp

最长递增子序列

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

状态转移方程的含义:位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

最长连续递增序列

dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]。

如果 nums[i] > nums[i - 1],那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。
即:dp[i] = dp[i - 1] + 1;

也就是不需要两重循环来穷举
因为递增的条件剪掉了很多


这里下标从0开始 相应的判断稍作调整


dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。
特别注意: “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串
在遍历dp[i][j]的时候i 和 j都要从1开始。

其实定义成当前位置开始也可以 这里是为了方便进行初始化
只需要初始化为0就行(也就是在java中不需要进行额外的初始化操作)

滚动数组版本

标签:结尾,递增,序列,长度,最长,dp
From: https://www.cnblogs.com/mingtiao/p/18024165

相关文章

  • python实战:使用json序列化
    一,官方文档:https://docs.python.org/zh-cn/3/library/json.html二,json与字典的相互转化1,字典转json字符串1234567importjson #字典转jsond=dict(name='Tom',age=2,score=88)json_d=json.dumps(d)print(type(json_d))print(json_d)......
  • P2023 [AHOI2009] 维护序列
    原题链接code#definelllonglong#include<bits/stdc++.h>usingnamespacestd;lltree[410000]={0};llwait_mul[410000]={0};llwait_add[410000]={0};lln,p;inlinevoidread(ll&x){x=0;llflag=1;charc=getchar();while(c......
  • rust结构体包含另一个结构体引用时,serde序列化问题
    代码如下useserde::{Deserialize,Serialize};#[derive(Serialize,Deserialize)]structPerson{id:String,name:String,}#[derive(Serialize,Deserialize)]structMsg<'a>{id:String,person:&'aPerson,}fnmain(){......
  • DP19 最长公共子序列(一)C
    建议直接网上看思路....#include<stdio.h>intmax(inti,intj){if(i>j)returni;returnj;}intmaxlength[1001][1001];intmain(){intn,m;while(scanf("%d%d",&n,&m)!=EOF){charc=getchar();//读取换行char......
  • KY78 最大上升子序列和C++
    这个解决问题的思路使用动态规划,即用已知状态去得到未知状态。思路逻辑是这样sum[i]记录以A[i]为末上升子序列的和的最大值然后从j从0-i-1遍历如果A[j]<A[i]那么sum[i]=sum[j]+A[i];然后找出sum[i]中的的最大值,就是以A[i]为末上升子序列的和的最大值。这样就实现了从前......
  • day29 回溯算法part5 代码随想录算法训练营 491. 非递减子序列
    题目:491.非递减子序列我的感悟:难不怕,不行就抄一遍,再默写一遍,多记忆几遍。加油!!!理解难点:uset是本层的, res收获的是节点(满足要求的节点),不用return(用了return是仅仅收集叶子节点的)判断的逻辑,是nums[i]当前的节点和目标的path的区别代码示例:classSolution:......
  • P3411 序列变换 题解
    自己做不出来,看现在题解区的题解讲的都不咋清楚。懂了之后来为后人铺路。而且我的马蜂比较好看题目传送门我能看懂这道题,主要是依靠了这篇题解的帮助。首先我们只关注数的相对关系,所以可以离散化。注意到值域\(10^6\),用数组离散化。这道题可以用贪心做。(有一些定义先往下看)......
  • JAVA基础-序列化
    1,什么是序列化?Java序列化是指把Java对象转换为字节序列的过程,而Java反序列化是指把字节序列恢复为Java对象的过程。2,序列化的使用场景永久性保存对象,保存对的字节序列到本地文件或者数据库中;通过序列化以字节流的形式对象在网络中进行传递和接收;通过序列化在进程间传递......
  • 递增子序列--连续与不连续
    问题一:最长严格递增子序列的长度题目:给定一个整数数组nums,找到其中最长严格递增子序列的长度。状态定义:dp[i]表示以nums[i]结尾的最长严格递增子序列的长度。状态转移方程对于每个nums[i],遍历其之前的所有元素nums[j](j从0到i-1),如果nums[i]>nums[j],则可以考虑......
  • KY22 最大序列和C
    题目例子给的很好,还有不要遗漏全是负数的情况。#include<stdio.h>#include<math.h>intmain(){longlongn=0;while(scanf("%ld",&n)!=EOF){longlongsum=0;longlongmax=0;inttag=0;longlongmaxn=pow(-2,63);......