Show problems as
Classic problem #873MediumArrayHash TableDynamic Programming

Length of Longest Fibonacci Subsequence

Real-world version: The Longest Adding Ladder of Readings
Tracked in this browser only
Read Length of Longest Fibonacci Subsequence on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def len_longest_fib_subseq(gauges: list[int]) -> int:
Java
public int lenLongestFibSubseq(int[] gauges)

More on the same topics