我們如何確保Bitonic序列將從一個最長的遞增子序列和一個最長的遞減子序列形成？

例如我們有一個array[]={1,3,2,7,4,6,8,9}。我們如何確保Bitonic序列將從一個最長的遞增子序列和一個最長的遞減子序列形成？

這個array[]={1,3,4,6,8,9}的最長增長子序列及其長度= 6。

這個array[]={3,2}的最長遞減的子序列及其長度= 2。

然後是這個array[]={1,3,4,6,8,9}的Bitonic子序列？如果是，那麼它的長度= 6。但是，Bitonic子序列的長度= lis的長度+ lds -1的長度，這裏它們是不相等的。

如果沒有你怎麼能證明雙調子的那個長度= LIS的長度+長度LDS-1

糾正我，如果我錯了。謝謝。

來源

2015-05-29 Varun Teja

我認爲你錯過了雙聲道子序列的長度應該是「長度的lis」+「lds的長度」 - 「在lis和lds中出現的項目的數量」。另外，不應該你的雙向子序列包含來自lds的「2」嗎？ – twalberg

@twalberg給定一個包含n個正整數的數組A [0 ... n-1]，如果存在ak且i <= k <= j使得A [i] <= A，則子數組A [i，j] [i + 1] ... <= A[k] > = A [k + 1]> = .. A [j-1]> = A [j]。。我從geeksforgeeks中找到了這個，所以如何包含2。 –

公式是正確的，只給出6 ...考慮LIS []（作爲LIS數組）和LDS []（作爲LDS數組）。現在，當你從左到右迭代時，你到達了位置LIS [index] = 6即LIS至array [7]爲6 ..現在LDS [index = 7]爲1（一個元素是系列的最大長度）... NOW LIS [7] + LDS [7 ] -1 =（6 + 1-1）

現在你想要的雙音序列的證明... LIS [i]，LDS [i]表示直到我的最長遞增/遞減序列！現在，最終你想最大化它，這就是爲什麼你搜索的樣本空間！所以答案將是（LIS [i] + LDS [i] -1）的最大值0 < = i < = n-1 ... -1是由於重複包含第i個元素的位置！

來源

2015-06-02 09:28:21

我們如何確保Bitonic序列將從一個最長的遞增子序列和一個最長的遞減子序列形成？

回答

相關問題