Hide
Problem B
Fake Arithmetic Sequence
This problem has nothing to do with Arithmetic Sequence, but
I thought it did, hence the name.
You’re given a sequence $a$ of length $n$ containing only integers. Find the
longest subsequence $b$ of
$a$ such that for all
$3 \leq i \leq length(b)$,
$b[i] = b[i-1] + b[i-2]$
(Elements of $b$ are
enumerated starting from 1).
The sequence $b$ is a subsequence of sequence $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements.
Input
The first line contains a single integer $n$ ($ 1
\leq n \leq 500$).
The second line contains $n$ integers $a_ i$ ($ -10^9 \leq a_ i \leq 10^9$).
Output
A single integer - the length of the longest subsequence $b$
| Sample Input 1 | Sample Output 1 |
|---|---|
7 0 3 20 6 20 9 40 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 36 86 -74 39 -99 71 66 |
2 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 45 -16 -78 -94 -20 -10 -67 100 -30 -40 |
4 |
