Q

第二长的递增子序列的长度

2016-09-25 76 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

相关问题