没有合适的资源?快使用搜索试试~ 我知道了~
解题思路27
需积分: 0 0 下载量 57 浏览量
2022-08-03
11:37:15
上传
评论
收藏 434KB PDF 举报
温馨提示
试读
5页
1、 对于 a[n]来说,由于它是最后一个数,所以当从 a[n]开始查找时,只存在长度为 1 的不 2、 若从 a[n-1]开始查找,则存在下面的两种可能性:
资源详情
资源评论
资源推荐
最长上升子序列
1 题目描述
广场上站着一支队伍,她们是来自全国各地的扭秧歌代表队,现在有她们的身高数据,请你帮
忙找出身高依次递增的子序列。 例如队伍的身高数据是(1、7、3、5、9、4、8),其中依次递增
的子序列有(1、7),( 1、3、5、9),( 1、3、4、8)等,其中最长的长度为 4。
1.1 输入描述:
输入包含多组数据,每组数据第一行包含一个正整数 n(1≤n≤1000)。 紧接着第二行包含 n
个正整数 m(1≤n≤10000),代表队伍中每位队员的身高。
1.2 输出描述:
对应每一组数据,输出最长递增子序列的长度。
1.3 输入例子:
7
1 7 3 5 9 4 8
6
1 3 5 2 4 6
1.4 输出例子:
4
4
2 解题思路
这题目是经典的 DP 题目,也可叫作 LIS(Longest Increasing Subsequence)最长上升子
序列或者最长不下降子序列。很基础的题目,有两种算法,复杂度分别为 O( )和 O(
)。
2.1 O(
)算法分析
假设 a[0:n]是给定的序列(长度为 n+1,下标从 0 到 n)
1、 对于 a[n]来说,由于它是最后一个数,所以当从 a[n]开始查找时,只存在长度为 1 的不
下降子序列;
老光私享
- 粉丝: 81
- 资源: 255
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0