确定哪些项目在数组中的最长递增子序列的一部分（S）

问题描述

这是最长递增子序列问题的变体。假设，而不是希望找到一个序列或counting多少个序列有，你要确定能成为其中的一部分项目的部分的最长递增序列。

This is a variant of the longest increasing subsequence problem. Suppose that, instead of wanting to find a sequence or counting how many sequences there are, you wanted to identify items that can be part of some longest increasing sequence.

例如，在列表中 1,2,4,3,0,5 除零的所有项目可以是最长递增子序列的一部分。

For example, in the list 1,2,4,3,0,5 all items except the zero can be part of a longest increasing subsequence.

什么是战略，找到这些项目？如何高效能不能做到？

What is a strategy to find these items? How efficiently can it be done?

推荐答案

一种方法是使用相同的动态算法如在最长递增子问题，跟踪最好项至precede的我'个项目假设它是最后一个项目，但调整它来跟踪联系。然后，在最佳preceding物品是公知的每一个项目，确定哪些项目是通过该图形可到达从得分最高的项目开始时

One method is to use the same dynamic algorithm as in the longest increasing subsequence problem, keeping track of the best item to precede the i'th item assuming it was the last item, but tweak it to keep track of ties. Then, after the best preceding items are known for every item, determine which items are reachable via that graph when starting from the top scoring items.

在本例的情况下， 1,2,4,3,0,5 ，它的工作是这样的：

In the case of the example, 1,2,4,3,0,5, it would work like this:

• 1 为指数0，所以给它的1 LIS得分没有previous指数
• 2 可以是 1 pceded $ P $，所以 2 获取1 + 1 = 2 LIS分和0
• 4 可以是 2 pceded $ P $和 1 ，而 2 有一个更好的LIS成绩这么 4 获得的2 + 1 = 3 LIS评分， 1
系统previous指数
• 3 可也$由 2 pceded p $和 1 ，并再次 2 有一个更好的LIS成绩这么 3 获得的2 + 1 LIS得分= 3和1
系统previous指数
• 0 不能被任何pceded $ P $，所以它得到了1分LIS没有previous指数
• 5 可以是其他任何物品pceded $ P $，但 3 和 4 有最好的LIS评分（= 3），因此 5 获得的3 + 1 = 4 LIS评分与previous指标为2或3。

• 1 is at index 0, so give it a lis score of 1 with no previous index
• 2 can be preceded by 1, so 2 gets a lis score of 1+1=2 and a previous index of 0
• 4 can be preceded by 2 and 1, but 2 has a better lis score so 4 gets a lis score of 2+1=3 and a previous index of 1
• 3 can be also preceded by 2 and 1, and again 2 has a better lis score so 3 gets a lis score of 2+1=3 and a previous index of 1
• 0 can't be preceded by anything, so it gets a lis score of 1 with no previous index
• 5 can be preceded by any of the other items, but 3 and 4 have the best lis scores (=3) so 5 gets a lis score of 3+1=4 with previous indexes of 2 or 3.

现在我们来得分最高的项目，只需 5 在这种情况下，并反复向后搜索，可以precede它的项目。这将标志着 5 ， 3 ， 4 ， 2 和 1 （而不是 0 ）的可-BE-在-最长的序列。

Now we take the top scoring items, just 5 in this case, and iteratively search backwards for items that can precede it. This will mark 5, 3, 4, 2 and 1 (but not 0) as can-be-in-longest-sequence.

这绝对是运行为O（n ^ 2）的时候，我认为通过合理地就可以取得 0的工作（N LG N）的时间。

This definitely runs in O(n^2) time, and I think by being clever it can be made to work in O(n lg n) time.

从二次时候都会面临的主要挑战是赚不到明确的图，能够最佳precede'的边缘。如 1,1,1,1,1,1，......，2,2,2,2,2,2，... A名单有一个二次边数，所以你需要避免将其储存全部或探索它们。

The main challenge for going from quadratic time is not making an explicit graph with 'can optimally precede' edges. A list like 1,1,1,1,1,1,...,2,2,2,2,2,2,... has a quadratic number of edges, so you need to avoid storing them all or exploring them all.

这篇关于确定哪些项目在数组中的最长递增子序列的一部分（S）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！