• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Processing Letters >An algorithm for solving the longest increasing circular subsequence problem
【24h】

An algorithm for solving the longest increasing circular subsequence problem

机译：一种求解最长增长循环子序列问题的算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The problem of finding a longest increasing circular subsequence (LICS) [1] in a sequence of integers is to find a longest subsequence of any rotation of a given sequence (a subsequence is obtained by removing zero or more elements) such that each integer of the subsequence is smaller than the integer that follows it. The LICS problem is a generalization of a classic longest increasing subsequence (US) problem, with applications in several areas, e.g., research on genomes [5] and as a tool for solving the widely known longest common subsequence problem [6]. The proved worst-case time lower bound for US is Ω(n log n) in the comparison model [6]. When the sequence is a permutation of all integers from the range |l,n|, in the RAM model this result can be improved to Ω(n log log n) by using van Emde Boas trees [4].
机译：在整数序列中找到最长的递增循环子序列（LICS）[1]的问题是要找到给定序列的任何旋转的最长子序列（子序列是通过删除零个或多个元素获得的），使得每个整数子序列小于其后的整数。 LICS问题是经典的最长增长子序列（US）问题的一般化，在多个领域都有应用，例如，对基因组的研究[5]，并且是解决众所周知的最长的常见子序列问题的工具[6]。在比较模型中，已证明的US的最坏情况时间下限是Ω（n log n）[6]。当序列是| l，n |范围内所有整数的置换时，在RAM模型中，可以通过使用van Emde Boas树[4]将结果提高到Ω（n log log n）。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号