首页 > 编程语言 >代码随想录算法训练营第四十天| 300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组

代码随想录算法训练营第四十天| 300.最长递增子序列 674. 最长连续递增序列 718. 最长重复子数组

时间:2023-07-28 10:35:12浏览次数:38  
标签:nums 递增 result 序列 最长 dp

300.最长递增子序列

要求:

可以删减任意个节点,最后保存最大的递增长度

难点:

4 10 4 8 9

如何 保证全局的视角,看到很前面的节点是否大于当前的节点,而不是仅仅记录状态

思路:

dp[n] , 当子序列的末尾为N时,它的最大子序列长度

也就意味着,N在它的子序列中是最大的,遍历这个N之前的所有序列,如果比他们大,就+1

注意, 2 1 3, 虽然3 比1 2都大,但是为2,

如何做到这一点?

dp[i] = max(dp[i], dp[j]+1),所以2 当时是1,1也是1,所以3是2,而不会是3

代码:

 1 // 要求:最长严格递增子序列长度 可以删除任意节点
 2 // 难点:如何全局的看到后面的情况0
 3 // 
 4 // dp[n] : 以nums[n]为结尾的最长递增子序列的长度!!! 很重要
 5 // 
 6 // dp[i] = 因为是以I为结尾,所以需要把I之前的所有节点都遍历一下,找到目前最长的子序列长度
 7 //
 8 int lengthOfLIS(vector<int>& nums) {
 9     if (nums.size() == 1) return 1;
10 
11     vector<int>dp(nums.size(), 1);
12 
13     for (int i = 1; i < nums.size(); i++)
14     {
15         // 从而实现了全局,也就是4 10 4 8 9 的问题, dp[i] = dp[i-1]+1 , dp[i-1]
16         for (int j = 0; j < i; j++)
17         {
18             if (nums[j] < nums[i])
19             {
20                 //很巧妙 一定要会用
21                 dp[i] = max(dp[i], dp[j] + 1);
22             }
23         }
24     }
25 
26     int result = INT_MIN;
27     for (int i = 0; i < dp.size(); i++)
28     {
29         result = result > dp[i] ? result : dp[i];
30     }
31 
32     return result;
33 }

 

标签:nums,递增,result,序列,最长,dp
From: https://www.cnblogs.com/smartisn/p/17586908.html

相关文章

  • 比JDK最高快170倍,蚂蚁开源一款序列化框架!
    点击“终码一生”,关注,置顶公众号每日技术干货,第一时间送达! Fury是一个基于JIT动态编译和零拷贝的多语言序列化框架,支持Java/Python/Golang/JavaScript/C++等语言,提供全自动的对象多语言/跨语言序列化能力,和相比JDK最高170倍的性能。GitHub地址为:https://github.com/al......
  • P2127 序列排序 题解
    原题题目意思\(有一个数列a,每次可以挑选任意两个元素交换位置,代价为这两个元素的和,问把序列a升序排序所需的最小总代价\)\(定义数列上的一个有i个元素的环S使得s_1要换到s_2,s_2要到s_3,……,s_i要到s_1\)\(原图一个元素只有一个目标位置,所以可以看作一个有n点,n边的有向图\)......
  • 2023-07-27:最长可整合子数组的长度, 数组中的数字排序之后,相邻两数的差值是1, 这种数组
    2023-07-27:最长可整合子数组的长度,数组中的数字排序之后,相邻两数的差值是1,这种数组就叫可整合数组。给定一个数组,求最长可整合子数组的长度。答案2023-07-27:算法maxLen的过程如下:1.检查输入数组是否为空,如果为空,则返回0,表示最长可整合子数组长度为0。2.初始化长度为1的最长......
  • PHP 中优雅的将JSON/XML/YAML 等数据反序列化成指定的类对象
    这个小事情何以需要记上一笔?实在是因为当用了各种编程语言以后,发现系统I/O处,尤其对外的接口Interface最重要,它或许可以被称为Specification,规约。PHP是混合型编程风格的语言,不强求完全的OOP。但是代码不OOP化的话,又得不到更多的开发工具的支持。尤其在PHP中如果只是用数组结......
  • 关于视图类和序列化类的知识
    1.代码classPayOrderView(GenericViewSet):serializer_class=PaySerializerdefcreate(self,request,*args,**kwargs):ser=self.get_serializer(context={'request':request},data=request.data)ser.is_vaild(raise_exceptio......
  • JAVA 序列化(创建可复用的 Java 对象)
    保存(持久化)对象及其状态到内存或者磁盘Java平台允许我们在内存中创建可复用的Java对象,但一般情况下,只有当JVM处于运行时,这些对象才可能存在,即,这些对象的生命周期不会比JVM的生命周期更长。但在现实应用中,就可能要求在JVM停止运行之后能够保存(持久化)指定的对象,并在将......
  • 2023-07-25:你驾驶出租车行驶在一条有 n 个地点的路上 这 n 个地点从近到远编号为 1 到
    2023-07-25:你驾驶出租车行驶在一条有n个地点的路上这n个地点从近到远编号为1到n,你想要从1开到n通过接乘客订单盈利。你只能沿着编号递增的方向前进,不能改变方向乘客信息用一个下标从0开始的二维数组rides表示其中rides[i]=[starti,endi,tipi]表示第i位......
  • 2023-07-25:你驾驶出租车行驶在一条有 n 个地点的路上 这 n 个地点从近到远编号为 1 到
    2023-07-25:你驾驶出租车行驶在一条有n个地点的路上这n个地点从近到远编号为1到n,你想要从1开到n通过接乘客订单盈利。你只能沿着编号递增的方向前进,不能改变方向乘客信息用一个下标从0开始的二维数组rides表示其中rides[i]=[starti,endi,tipi]表示第i位乘客需......
  • 帆软channel反序列化漏洞
    一级测试一级级测试测试二级测试测试三级测试二级测试......
  • 数据分享|SAS与eviews用ARIMA模型对我国大豆产量时间序列预测、稳定性、白噪声检验可
    全文链接:http://tecdat.cn/?p=31480最近我们被客户要求撰写关于ARIMA的研究报告,包括一些图形和统计输出。我国以前一直以来都是世界上大豆生产的第一大国。但由于各国的日益强大,导致我国豆种植面积和产量持续缩减。因此,预测我国的大豆产量对中国未来的经济发展有着极其重要的作......