Q

第二長的遞增子序列的長度

2016-09-25 72 views -2 likes

-2

你必須用O（n^2）來解決它。（這是可以等於與LIS的長度，例如「13245」）第二長的遞增子序列的長度

2016-09-25 PythonYXY

+0

是否有一個原因，它不會只是LIS的長度減1？ –

+0

那麼，「13245」的答案是4，與LIS的長度相同。 – PythonYXY

+0

所以它不是第二長的。它等於或小於，因此問題實際上是檢查是否存在與最長的相同大小的另一個增加的子序列。如果不是，答案將是LIS-1。 –

A

回答

0

這個問題可以簡化爲：如果存在兩個或更多個不同的LIS的（當然是相同的最大長度

檢查）。
如果答案是肯定的 - 「第二」-LIS顯然與LIS長度相同。
如果答案是否定的 - 第二LIS長度最長的一次減1

長度爲了找到你可以簡單地修改O(n^2)算法描述here跟蹤不僅LIS的數量最大長度，但也是最大數量。

2016-09-25 15:00:52

相關問題