Самая длинная подпоследовательность, в которой целое число на выходе в 5 раз больше предыдущего

Question

Я тренируюсь с проблемами UVA, и я застрял в этом. Мне нужно получить самую длинную подпоследовательность, где последовательные целые числа в 5 раз больше, чем предыдущие

выборка ввода: 7, 100, 3, 80, 3, 5, 18, 25, 73, 125, выход: 3 (5, 25, 125)

Я подумал о решении, но потребуется n^n, где я сравниваю целое число с остальными целыми числами, что не является идеальным. возможно ли более быстрое решение?

Answer 1

Если вы просмотрите список и составите карту значений, которые вы видели до сих пор, сопоставив их с длиной последовательности, заканчивающейся на этом числе, вы можете решить эту проблему в 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 []

Answer 2

Поскольку решение должно дать только одно лучшее решение, можно отбросить некоторые частичные решения. Такие решения всегда идут с некоторой тонкой моделью данных, выкристаллизованной из требований. Предположим, у вас есть индекс i поддержал все возможные подпоследовательности вплоть до i - 1,

Из этих подпоследовательностей интерес представляет только последний элемент (хвост).

1. Элемент может начать новую последовательность, только если он не может быть добавлен к существующей последовательности (и 3. нет последовательности с хвостом <= item).
2. Где возможно, последовательность может добавить элемент, чтобы сформировать дополнительную новую последовательность.
3. Более короткая последовательность должна иметь хвост меньше, чем у более длинной последовательности

Точка 3 интересна тем, что для каждой длины этих последовательностей вам нужна только одна последовательность с самым низким хвостом.

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

Для нового элемента можно выполнить бинарный поиск для элемента /5 в диапазоне 0 .. индекс наибольшей последовательности = item.

Так O(n.log n),