The Fibonacci Segment · Interview Problem

Back to problems

Codeforces

Easy

Arrays

Math

Strings

The Fibonacci Segment

Find the longest contiguous segment whose values follow the Fibonacci rule after the first two elements.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Fibonacci Segment

gfg

Problem Statement

You are given an array of integers. Your task is to find the length of the longest contiguous segment in which every element from the third one onward is equal to the sum of the two previous elements.

In other words, for a segment $a[l..r]$ , it is valid if for every $i$ with $l+2 \le i \le r$ , the condition $a_i = a_{i-1} + a_{i-2}$ holds.

Return the maximum possible length of such a segment. If no segment longer than 1 exists, the answer is 1. If a pair of consecutive elements forms a valid segment of length 2, that is also allowed.

Input Format

The first line contains an integer $n$ — the number of elements.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ .

Output Format

Print a single integer — the maximum length of a contiguous Fibonacci-like segment.

Constraints

$1 \le n \le 10^5$
Elements fit in 32-bit signed integers
A linear-time solution is expected

Examples

Sample cases returned by the problem API.

Example 1

Input

5
1 2 3 5 8

Output

Explanation

The entire array is a valid Fibonacci-like segment.

Example 2

Input

6
4 1 5 6 11 1

Output

Explanation

The segment [1, 5, 6, 11] has length 4 and satisfies the rule: 6 = 1 + 5, 11 = 5 + 6.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress