• 板块学术版
  • 楼主Jasonsheng
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/11/21 15:51
  • 上次更新2023/11/3 23:49:24
查看原帖
95537
Jasonsheng楼主2021/11/21 15:51

给定一个长度为 n 的序列 ,请求出它的最长上升子序列的长度,以及有多少个位置上的元素可能出现在最长上升子序列中,多少个位置上的元素一定出现在最长上升子序列中?

例如,给定序列 3,1,2,5,4中:

{1,2,5}与{1,2,4}均为满足条件的最长上升子序列,该序列的最长上升子序列的长度为3。

元素1,2,4,5 均有可能出现在最长上升子序列中,故有 4 个位置上的元素可能出现在最长上升子序列中,

而元素 1,2 必然出现在最长上升子序列中,故有 2 个位置上的元素一定出现在最长上升子序列中。

2021/11/21 15:51
加载中...