例如,我们有一个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的长度?
如果我错了,请纠正我。谢谢。
发布于 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位置重复包含了元素!。
https://stackoverflow.com/questions/30533790
复制相似问题