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

I'm practicing with UVA problems and I'm stuck in this. I need to get the longest subsequence where the consecutive integers are 5 times greater than the previous

sample input: 7, 100, 3, 80, 3, 5, 18, 25, 73, 125 output: 3 (5, 25, 125)

I thought of a solution but it will take n^n where I compare an integer with the rest of the integers, which is not ideal. is it possible for a faster solution?

If you traverse the list and build up a map of the values seen so far, mapped to the length the sequence ending in that number, you can solve the problem in O(n).

Given your sample list of 7, 100, 3, 80, 3, 5, 18, 25, 73, 125, the resulting map would be:

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

Longest sequence is 3, ending in value 125. We can now build the sequence by reverse-calculating it: 125 → 25 → 5

Here is the code (not using Java 8 features):

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));
}

Test

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();

Output

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