java - 输出中的整数比前一个整数大 5 倍的最长子序列

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 3 年前。

Improve this question

我正在练习 UVA 问题，但我陷入了困境。我需要得到最长的subsequence其中连续整数比前一个大 5 倍

样本输入:7, 100, 3, 80, 3, 5, 18, 25, 73, 125输出:3 (5, 25, 125)

我想到了一个解决方案，但需要 n^n 来将一个整数与其余整数进行比较，这并不理想。有可能有更快的解决方案吗？

Answer 1

由于解决方案只需给出一个最佳解决方案，因此可以放弃一些部分解决方案。此类解决方案总是伴随着一些根据需求具体化的精细数据模型。假设您有一个索引 i 维护着 i - 1 之前的所有可能的子序列。

在这些子序列中，只有最后一项(尾部)是令人感兴趣的。

1. 仅当该项目无法添加到现有序列时(并且 3. 不存在 tail <= item 的序列)，该项目才能启动新序列。
2. 在可能的情况下，序列可以添加项目以形成额外的新序列
3. 较短的序列的尾部应小于较长序列的尾部

第 3 点很有趣，因为它意味着对于这些序列的每个长度，您只需要 1 个序列，且尾部最低。

Sequence[] sequencesByLength = new Sequence[n];
// sequencesByLength[i] < sequencesByLength[j] <=> i < j

对于新项目，可以在 0 .. 最高序列索引 < i 范围内对 item/5 进行二分搜索。假设您可以将其添加到位置 k，那么当 k+1 的尾部 >= item 时，可以将新序列添加到 k+1。

所以O(n.log n)。