需要了解算法的答案

我想解決以上使用JavaScript的最長單調遞增子序列問題。爲了做到這一點，我需要知道最長單調子序列。目前我正在關注wikipedia文章。我不理解這個例子的是，從0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, …列表中列出的最長的子序列爲0, 2, 6, 9, 13, 15。問題是爲什麼答案在2到6之間沒有3，在6到9之間沒有8等？這個答案是如何來自該清單的？需要了解算法的答案

來源

2014-09-27 2619

這是因爲這在原始數組中也沒有發生。 – 2014-09-27 08:14:35

取決於子序列的定義。 – 2014-09-27 08:25:54

@匿名可以請你舉個例子詳細回答一下嗎？ – 2619 2014-09-27 08:54:43

最後，考慮名稱「最長單調遞增子序列」。所以，從給定的數組中，你需要找出數字應該以嚴格遞增的方式出現的最大序列。可以有很多序列，其中子陣列可以嚴格增加，但你需要找到最大的子陣列。

所以。讓我們調試這個數組。 a [] = {0,8,4,12,2,10，6,14,1,9,5,13,3,11,7,15}

在這裏，一些單調遞增的子陣列有：

{0,8,12,14,15}長度= 5

{0,4,12,14,15}長度= 5

{0,1,9,13 ，15}長度= 5等等。

但如果計算這樣，就可以找到最大的子陣列將是：

{0,2，6，9，13，15}，長度= 6，所以這是回答。

每次你選擇任何數字時，下一個數字應該比前一個數字大，並且必須出現在數組中。例如{0,2,6,9,13,15}這個列表，當你選擇，那麼下一個數字應該大於9.即時序列顯示13> 9，所以你可以選擇。你也可以選擇11.但是這會創建子數組的另一個分支。像： {0,2,6,9,11,15}這是另一種解決方案。

希望這個解釋能幫助你理解LIS（增長最長的子序列）。謝謝。

來源

2014-09-27 09:01:06 verbose

首先，你的問題的標題說：最長的CONTIGUOUS子序列，這是LIS的原始問題的輕微變化，其中結果不需要具有來自原始數組的連續值，如在上面的例子中指出的。按照此鏈接，其具有爲O（n^2）解決方案，它可以被優化爲具有O（nlogn）溶液於LIS算法體面的解釋： http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

爲LIS的連續變型，這裏是一個體面解決方法： http://worldofbrock.blogspot.com/2009/10/how-to-find-longest-continuous.html

來源

2014-09-28 03:27:24 akella

你的第二個鏈接不返回數組。如果你可以在這裏發佈一個示例答案和返回數組的代碼，那將會很好。 – 26ph19 2014-10-01 10:36:22

需要了解算法的答案

回答

相關問題