1102MediumArrayHash TableDynamic Programming

The Longest Adding Ladder of Readings

Tracked in this browser only

Trains the technique from

LeetCode 873Length of Longest Fibonacci Subsequence

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

The list gauges is strictly increasing. A ladder is a selection of three or more of its readings, kept in the order they appear in the list, where every reading after the first two equals the sum of the two readings before it.

Return the length of the longest ladder, or 0 when the list holds none.

Examples

Example 1

Input: gauges = [1, 2, 3, 5, 8, 13, 21]
Output: 7

Every reading from the third onwards is the sum of the two before it, so the whole list is one ladder.

Example 2

Input: gauges = [1, 2, 4]
Output: 0

No reading is the sum of two earlier ones, so there is no ladder at all.

Example 3

Input: gauges = [3, 6, 9, 12, 15, 18, 21, 24]
Output: 5

Take 3, 6, 9, 15 and 24: each rung is the sum of the two before it. A sixth rung would have to be 39, which the list does not hold.

Constraints

3 <= gauges.length <= 1000
1 <= gauges[i] <= 10^9
gauges is strictly increasing

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def len_longest_fib_subseq(gauges: list[int]) -> int:

Java

public int lenLongestFibSubseq(int[] gauges)

The intended approach

Time O(n^2) over the pairs of readings.Space O(n^2) for the length held against each pair.

Two readings settle everything that follows them: once a ladder's last two rungs are known, the next rung is forced. So the thing worth remembering is not a single reading but a pair of them, and the fact worth keeping is how long a ladder can end on that pair. Walk every pair of positions with the earlier one first. For a pair, whatever came before it is decided too: the rung before must equal the later reading minus the earlier one, and it must sit earlier in the list than the pair's first reading. A lookup from reading to position finds it in one step, since the readings are all different. If such a rung exists, this pair's ladder is one longer than the ladder ending on that rung and the pair's first reading; otherwise the pair starts a ladder of its own, length two. Running the pairs with the second position outermost is not needed, only that the shorter ladder is settled first, which holds because the pair it depends on ends earlier in the list. A length of two means no reading was ever added, so anything under three is reported as none at all.

Pythonentry point: len_longest_fib_subseq

def len_longest_fib_subseq(gauges):
    n = len(gauges)
    where = {}
    for i in range(n):
        where[gauges[i]] = i
    length = {}
    best = 0
    for j in range(n):
        for k in range(j + 1, n):
            i = where.get(gauges[k] - gauges[j], -1)
            if i >= 0 and i < j:
                run = length.get((i, j), 2) + 1
            else:
                run = 2
            length[(j, k)] = run
            if run > best:
                best = run
    return best if best >= 3 else 0

The obvious version

Take every pair of readings as a ladder's opening two rungs and then walk forward: the next rung is forced to be their sum, so keep stepping while that sum is in the list and count the rungs. Costs the pair count times the length of the ladders it walks, with a set lookup at every step.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_len_longest_fib_subseq(gauges):
    n = len(gauges)
    present = set(gauges)
    best = 0
    for a in range(n):
        for b in range(a + 1, n):
            first = gauges[a]
            second = gauges[b]
            run = 2
            while first + second in present:
                first, second = second, first + second
                run += 1
            if run > best:
                best = run
    return best if best >= 3 else 0

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in