首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何保证由一个最长的递增子序列和一个最长的递减子序列构成二重子序列?

问如何保证由一个最长的递增子序列和一个最长的递减子序列构成二重子序列?
EN

Stack Overflow用户
提问于 2015-05-29 15:45:24
回答 1查看 210关注 0票数 0

例如,我们有一个array[]={1,3,2,7,4,6,8,9}。

此array[]={1,3,4,6,8,9}及其length=6的最长增长子序列。

此array[]={3,2}及其length=2的最长递减子序列。

那么这个array[]={1,3,4,6,8,9}的双离子子序列是吗?如果是,那么它的双子序列的length=6.But长度= lis的长度+ lds -1的长度,这里它们是不相等的。

如果没有,你如何证明lds-1的双离子subsequence=length of lis+length的长度?

如果我错了,请纠正我。谢谢。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-06-02 09:28:21

公式是正确的,只给出6.以LISas the LIS array和LDSas LDS array为例。现在,当您从左到右迭代时,就会到达LISindex=6的位置,即LIS,直到array7为6。现在LDSindex=7是1(一个元素是序列的最大长度).现在LIS7 7+LDS7-1=(6+1-1)

现在你想要的关于双离子序列的证据..。LISi,LDSi代表到i为止最长的增/减序列!现在,最终您想要最大化它,这就是为什么您搜索样本空间!因此,答案是(LISi+LDSi -1 ) 0<=i<=n-1 .-1是由于在I_ th位置重复包含了元素!。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/30533790

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档