我们如何保证一个双调序列由一个最长递增子序列和一个最长递减子序列组成？
How can we assure that a Bitonic sequence will be formed from one longest increasing subsequence and one longest decreasing subsequence?
例如我们有一个 array[]={1,3,2,7,4,6,8,9}.
此 array[]={1,3,4,6,8,9} 的最长递增子序列，其长度为 6。
此 array[]={3,2} 的最长递减子序列，其长度为 2。
那么这个array[]={1,3,4,6,8,9}的双调子序列是？如果是那么它的长度=6.But双调子序列的长度=lis的长度+lds的长度-1，
这里他们不相等。
如果不是你怎么证明双调子序列的长度=lis的长度+lds-1的长度
如果我错了请纠正我。
谢谢。
公式是正确的，只给出 6...考虑 LIS[]（作为 LIS 数组）和 LDS[]（作为 LDS 数组）..现在当你从左到右迭代时，你到达LIS[index]=6 的位置，即 LIS 直到 array[7] 为 6.. 现在 LDS[index=7] 为 1（通常一个元素是系列的最大长度）...现在 LIS[7]+LDS[ 7]-1=(6+1-1)
现在你想要的双调数列的证明...
LIS[i],LDS[i]代表最长递增/递减序列直到i！
现在，最终您想要最大化它，这就是您搜索示例 space 的原因！所以答案将是最大的 (LIS[i]+LDS[i]-1) 0<=i<=n-1 ...
-1是因为重复包含了第i个位置的元素！
例如我们有一个 array[]={1,3,2,7,4,6,8,9}.
此 array[]={1,3,4,6,8,9} 的最长递增子序列，其长度为 6。
此 array[]={3,2} 的最长递减子序列，其长度为 2。
那么这个array[]={1,3,4,6,8,9}的双调子序列是？如果是那么它的长度=6.But双调子序列的长度=lis的长度+lds的长度-1，
这里他们不相等。
如果不是你怎么证明双调子序列的长度=lis的长度+lds-1的长度
如果我错了请纠正我。 谢谢。
公式是正确的，只给出 6...考虑 LIS[]（作为 LIS 数组）和 LDS[]（作为 LDS 数组）..现在当你从左到右迭代时，你到达LIS[index]=6 的位置，即 LIS 直到 array[7] 为 6.. 现在 LDS[index=7] 为 1（通常一个元素是系列的最大长度）...现在 LIS[7]+LDS[ 7]-1=(6+1-1)
现在你想要的双调数列的证明... LIS[i],LDS[i]代表最长递增/递减序列直到i！ 现在，最终您想要最大化它，这就是您搜索示例 space 的原因！所以答案将是最大的 (LIS[i]+LDS[i]-1) 0<=i<=n-1 ... -1是因为重复包含了第i个位置的元素！