最小最长连续离散子序列问题

无心人 · 发表于 2009-8-16 17:35:44

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

定义序列$L$，其子项为$a_i$，其中$i = 0$到$l - 1$ $l$称为序列$L$的长度,$i$称为$a_i$的位置如果有序列$L_p$，其子项均为$L$中的项且相邻的项位置维持为$L$中的顺序或者说，$L_p$是$L$中去掉若干项得到的则$L_p$称为$L$的离散子序列如果有$L_p$是某个自然数开始的连续整数称$L_p$是$L$的连续离散子序列假设有长度为10000的序列$L$，其项为$0$到$99$之间的随机整数现在求其连续离散子序列$L_p$ 满足 1、长度尽量长 2、子序列在原序列$L$中的位置之和最小求满足条件的序列

无心人 · 发表于 2009-8-16 17:40:05

比如序列 1，2，10，7，3，8，9，4，11，5 则 1，2，3，4，5是一个连续离散子序列 7，8，9也是 10，11也是

mathe · 发表于 2009-8-16 21:21:53

这个应该是线性时间复杂度问题

无心人 · 发表于 2009-8-17 08:53:29

哦我很犹豫是否把这个贴上来毕竟自己也感觉题目没啥新鲜东西不过呵呵既然想出来了索性就贴上吧

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 最小最长连续离散子序列问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。