首页 > 试题广场 >

给出一个由 n 个数组成的序列 A[1…n]

[单选题]

给出一个由 n 个数组成的序列 A[1…n] ，要求找出它的最长单调上升子序列，设 m[i] （ 1 ≤ i ≤ n ），表示以 A[i] 结尾的最长单调上升子序列的长度，则 m[1] = 1 ， m[i] （ 1 < i ≤ n ）为（ ）。 

  • m[i] = 1 + max{0，m[k]（A[k] < A[i]，1≤k < i ）}
  • m[i] = 1 + m[k] （k = i - 1 && i > 1）
  • m[i] = 1 + max{-1，m[k] （A[k] ≤ A[i]，1≤k < i ）}
  • m[i] = max{0，m[k]（A[k] < A[i]，1≤k < i ）}
查看正确选项
添加回答
_random头像 _random
这题的意思硬是没懂🤐
发表于 2019-02-20 20:07:57 回复(0)
zfun头像 zfun
看了答案才知道想表达什么，而且按这个答案子序列可以不连续，但题目没有说明？
编辑于 2018-06-17 09:20:42 回复(0)
赞花婆头像 赞花婆
设表示：从左向右扫描过来直到以元素结尾的序列，获得的最长上升子序列的长度，且子序列包含元素。

即，是从，……到中找最大的一个值，再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。

最后，所要求的整个序列的最长公共子序列长度为max{f(i): 1<=i<=n}

例如，对于序列：4  2  6  3  1  5  2

i

1

2

3

4

5

6

7

array

4

2

6

3

1

5

2

f(i)

1

1

2

2

1

3

2

发表于 2017-08-04 18:19:20 回复(2)
Tc.l头像 Tc.l
题目没看懂，蒙倒是蒙对了
发表于 2020-07-02 21:46:48 回复(1)
为你扣下F键头像 为你扣下F键
子序列不一定连续
发表于 2018-08-06 15:12:44 回复(0)
亦夜头像 亦夜
看了答案也没看懂，我是不是没救了🙂
发表于 2020-07-11 11:48:33 回复(21)
侯卿头像 侯卿
对着答案想一下递归就能明白了。m[k](…)的意思是，所有k符合括号里条件的m[k]集合。
编辑于 2018-01-11 20:12:29 回复(0)
yuoyuo头像 yuoyuo
动态规划中的状态转移方程
发表于 2022-02-24 23:36:18 回复(0)
asaltyfish头像 asaltyfish
注意一个坑。
m[i] 表示以 A[i] 结尾的最长单调上升子序列的长度
所以A[i]这个数一定要在
m[n]的值也不是A[n]的最长单调上升子序列的值
发表于 2018-03-25 16:31:52 回复(0)
牛冲冲头像 牛冲冲
https://blog.csdn.net/sinat_31790817/article/details/78348722
发表于 2022-03-03 17:13:08 回复(0)
谦虚的牛肉丸在学习头像 谦虚的牛肉丸在学习
应该是，1、先选出当前位置以前的单调连续上升子序列；2、之后比较当前位置和子序列的最后一个位置在数组位置上是否连续；3、连续则比较当前值和前一个位置的值大小，如果比他大则当前位置加入子序列，否则不加入；如果不连续，则返回之前选出的子序列长度；
发表于 2022-04-13 08:50:25 回复(0)
nanblack头像 nanblack
这个题就是经典的动态规划思路 用一个数组表示最长子序列长度
发表于 2021-04-03 18:43:21 回复(0)
kfc22头像 kfc22
经典的动态规划
发表于 2022-03-27 20:44:21 回复(0)
牛客77258588号头像 牛客77258588号
单看m[i]的定义，以A[i]结尾的最长单调上升子序列，所以在i及之前的这段上升子序列是一直连续的
发表于 2022-03-16 18:22:02 回复(1)
我从大数据中找个零头像 我从大数据中找个零
这题就是想问：解决最长单调子序问题的那个动态规划的转移式怎么写的。leetcode上面有个求数组的最长子序列题目，可以用动态规划解决。
发表于 2020-06-22 15:06:06 回复(0)
夕夕成玦玦头像 夕夕成玦玦

类似于dp列出状态转移方程就行了

发表于 2020-04-12 20:24:02 回复(0)
菜鸟九八号头像 菜鸟九八号
https://blog.csdn.net/morninghapppy/article/details/7643139
发表于 2020-03-09 10:20:25 回复(1)
金山银山头像 金山银山
太生草了，题意我懂，但没看出max式子怎么体现 A[i] 能不能加入之前的最长单调上升子序列
发表于 2025-04-08 21:22:08 回复(0)
牛客763455401号头像 牛客763455401号
不是以后是不是难一点的题目都是这样我看不懂
发表于 2024-08-11 23:17:54 回复(0)
ZGG_cs头像 ZGG_cs

对于最长单调上升子序列的长度 m[i]，它表示以 A[i] 结尾的最长单调上升子序列的长度。根据定义来看，我们需要考虑在 A[1...i-1] 中所有小于 A[i] 的元素，并找到它们中的最大值，并将其加一。

因此，最长单调上升子序列的长度可以通过以下公式计算：

m[i] = 1 + max{0，m[k]（A[k] < A[i]，1≤k < i ）}

这意味着我们要找到之前所有小于 A[i] 的元素中，以它们为结尾的最长单调上升子序列的长度，并取最大值。然后再将该结果加一，表示将当前元素 A[i] 加入到该子序列中。

选项 B 不正确，因为它仅考虑了前一个元素的最长单调上升子序列的长度，而没有考虑到之前所有小于 A[i] 的元素。

选项 C 也不正确，因为它考虑了不小于 A[i] 的元素，而不是小于 A[i] 的元素。

选项 D 也不正确，因为它没有将最大值加一。

发表于 2023-08-03 20:25:33 回复(0)
提交观点

问题信息

数组
上传者：赞花婆
难度：
25条回答 3863浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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