首页 > 试题广场 >

最长严格上升子数组(一)

[编程题]最长严格上升子数组(一)
  • 热度指数：3292 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为n的正整数数组nums，可以任意改变数组的其中一个元素，改变的元素范围也在[1,100000]之内，然后返回nums的最长"严格上升"子数组的长度。
1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
2.严格上升指在数组上任意位置都满足 nums[i] < nums[i+1]，比如[1,2,2,3]，其中[1,2,2]不是严格上升的子数组，[1,2]是的
数据范围： ，
要求： 空间复杂度 ，时间复杂度
示例1

输入

[7,2,3,1,5,6]

输出

5

说明

将1改为4，最长严格上升子数组为[2,3,4,5,6]
示例2

输入

[1,2,3,4]

输出

4

说明

最长严格上升子数组为[1,2,3,4]
示例3

输入

[1,2,2,3]

输出

3

说明

改变一个元素之后，最长严格上升子数组为[1,2,3]或者[2,3,4]，长度都为3
算法知识视频讲解
开通博客
头像 年底不被裁就算成功
发表于 2021-10-15 15:32:10
public class Solution { /** * 用left[i]表示以nums[i]结尾的最长严格上升子数组 用right[i]表示以nums[i]开始的最长严格上升子序列 * @param nums * @return */ public static int maxSub 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 KEY.L
发表于 2022-06-23 22:13:06
首先想好算法，一看最长上升子序列，那么比较脑子里应该出现几个dp式子： 接下来一看要求：空间复杂度 O (n) ，时间复杂度 O (n) 好家伙必须要on的复杂度 那么可以尝试结合其他算法去优化一个比较直接的dp，那么咱们首选二分！ 二分的思路如下： 先定义边界，l = 0, r = len, 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 姐姐的遮阳伞
发表于 2022-04-08 22:06:26
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 君鸿
发表于 2025-01-13 16:47:32
题目描述给定一个长度为n的正整数数组nums，可以任意改变数组的其中一个元素，原来的和改变的元素范围都在[1,100000]之内，然后返回nums的最长"严格上升"子数组的长度。1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3, 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 fagtttttt
发表于 2023-05-24 22:49:29
时间复杂度O(n),空间复杂度O(n)[C++ 代码] class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 神游星宇
发表于 2021-10-28 00:34:00
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 觉醒火龙果很想五点下课
发表于 2025-05-26 12:08:19
class Solution { public: int maxSubArrayLengthTwo(vector<int>& nums) { // 遍历每一个元素,向前以及向后检验,得以当前为断点得最长; // 或者,记录前一个序列的后端， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2024-07-01 20:22:04
import java.util.*; /** * NC155 最长严格上升子数组(一) * @author d3y1 */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客886831005号
发表于 2022-12-24 23:09:09
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客530210881号
发表于 2025-05-28 15:17:06
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @r 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 动态规划 穷举
上传者：牛客301499号
难度：
6条回答 5207浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长严格上升子数组(一)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号