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

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.

在这些子序列中，只有最后一项 (tail) 值得关注。

该项目只有在不能添加到现有序列中时才能开始一个新序列（并且3.没有尾部<=项目的序列）。
在可能的情况下，序列可以添加项目以形成额外的新序列
较短序列的尾部应小于较长序列的尾部

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

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

对于新项目，可以在 0 .. highest sequnce index < i 范围内对 item/5 进行二进制搜索。假设你可以将它添加到位置 k，然后可以将一个新序列添加到 k+1，当 k+1 的尾部 >= item.

所以O(n.log n).

Answer 2

如果您遍历列表并构建到目前为止看到的值的映射，映射到以该数字结尾的序列的长度，您可以在 O(n).

给定 7, 100, 3, 80, 3, 5, 18, 25, 73, 125 的示例列表，生成的地图将是：

7   → 1    ⇐ Not divisible by 5, so length=1
100 → 1    ⇐ 100 / 5 = 20, but 20 hasn't been seen, so length=1
3   → 1    ⇐ Not divisible by 5, so length=1
80  → 1    ⇐ 80 / 5 = 16, but 16 hasn't been seen, so length=1
3          ⇐ Skipped since 3 already in map
5   → 1    ⇐ 5 / 5 = 1, but 1 hasn't been seen, so length=1
18  → 1    ⇐ Not divisible by 5, so length=1
25  → 2    ⇐ 25 / 5 = 5, and 5 has length 1, so length=2
73  → 1    ⇐ Not divisible by 5, so length=1
125 → 3    ⇐ 125 / 5 = 25, and 25 has length 3, so length=3

最长序列为3，以125结尾。我们现在可以通过逆向计算构建序列：125 → 25 → 5

这是代码（没有使用Java 8个特征）：

private static void printLongestTimesFiveSequence(int ... input) {
    Map<Integer, Integer> valueLengthMap = new HashMap<>();
    int longestLength = 0, longestValue = 0;
    for (int value : input) {

        // Find length of sequence ending in 'value'
        int length = 1;
        if (value % 5 == 0) {
            Integer prevLength = valueLengthMap.get(value / 5);
            if (prevLength != null)
                length += prevLength;
        }

        // If length is new longest sequence, remember it
        if (length > longestLength) {
            longestLength = length;
            longestValue = value;
        }

        // Remember length of sequence ending in 'value' if first time seen,
        // or if longer than previously seen (e.g. for 15, 3, 15)
        Integer currentLength = valueLengthMap.get(value);
        if (currentLength == null || currentLength < length)
            valueLengthMap.put(value, length);
    }

    // Build sequence ending in value of remembered longest sequence
    int[] sequence = new int[longestLength];
    for (int i = longestLength - 1, value = longestValue; i >= 0; i--, value /= 5)
        sequence[i] = value;

    // Print result
    System.out.println(longestLength + " " + Arrays.toString(sequence));
}

测试

printLongestTimesFiveSequence(7, 100, 3, 80, 3, 5, 18, 25, 73, 125);
printLongestTimesFiveSequence(10, 50, 2);
printLongestTimesFiveSequence(15, 3, 75, 15, 75);
printLongestTimesFiveSequence(4, 20, 100, 20, 100);
printLongestTimesFiveSequence(5, 25, 125, 25, 125);
printLongestTimesFiveSequence();

输出

3 [5, 25, 125]
2 [10, 50]
3 [3, 15, 75]
3 [4, 20, 100]
3 [5, 25, 125]
0 []

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

Longest Subsequence where an integer in the output is 5 times greater than the previous

java

adhoc