Length of Longest Fibonacci Subsequence

MediumDynamic Programming2d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A sequence x1, x2, ..., xk is **Fibonacci-like** if k >= 3 and x(i) + x(i+1) == x(i+2) for every valid i. Given a **strictly increasing** array arr of positive integers, return the length of the longest Fibonacci-like subsequence of arr. A subsequence keeps the original order but may skip elements. If no such subsequence exists, return 0. An O(n^2) solution is expected.

Examples

Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
`[1,2,3,5,8]` is Fibonacci-like.
Input: arr = [1,3,7,11,12,14,18]
Output: 3
For example `[1,11,12]`, `[3,11,14]`, or `[7,11,18]`; none can be extended.

Constraints

  • `3 <= arr.length <= 1000`
  • `1 <= arr[i] < arr[i+1] <= 10^9`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 2d dp problems