|
| 1 | +<h2><a href="https://leetcode.com/problems/length-of-longest-fibonacci-subsequence">905. Length of Longest Fibonacci Subsequence</a></h2><h3>Medium</h3><hr><p>A sequence <code>x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub></code> is <em>Fibonacci-like</em> if:</p> |
| 2 | + |
| 3 | +<ul> |
| 4 | + <li><code>n >= 3</code></li> |
| 5 | + <li><code>x<sub>i</sub> + x<sub>i+1</sub> == x<sub>i+2</sub></code> for all <code>i + 2 <= n</code></li> |
| 6 | +</ul> |
| 7 | + |
| 8 | +<p>Given a <b>strictly increasing</b> array <code>arr</code> of positive integers forming a sequence, return <em>the <strong>length</strong> of the longest Fibonacci-like subsequence of</em> <code>arr</code>. If one does not exist, return <code>0</code>.</p> |
| 9 | + |
| 10 | +<p>A <strong>subsequence</strong> is derived from another sequence <code>arr</code> by deleting any number of elements (including none) from <code>arr</code>, without changing the order of the remaining elements. For example, <code>[3, 5, 8]</code> is a subsequence of <code>[3, 4, 5, 6, 7, 8]</code>.</p> |
| 11 | + |
| 12 | +<p> </p> |
| 13 | +<p><strong class="example">Example 1:</strong></p> |
| 14 | + |
| 15 | +<pre> |
| 16 | +<strong>Input:</strong> arr = [1,2,3,4,5,6,7,8] |
| 17 | +<strong>Output:</strong> 5 |
| 18 | +<strong>Explanation:</strong> The longest subsequence that is fibonacci-like: [1,2,3,5,8].</pre> |
| 19 | + |
| 20 | +<p><strong class="example">Example 2:</strong></p> |
| 21 | + |
| 22 | +<pre> |
| 23 | +<strong>Input:</strong> arr = [1,3,7,11,12,14,18] |
| 24 | +<strong>Output:</strong> 3 |
| 25 | +<strong>Explanation</strong>:<strong> </strong>The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].</pre> |
| 26 | + |
| 27 | +<p> </p> |
| 28 | +<p><strong>Constraints:</strong></p> |
| 29 | + |
| 30 | +<ul> |
| 31 | + <li><code>3 <= arr.length <= 1000</code></li> |
| 32 | + <li><code>1 <= arr[i] < arr[i + 1] <= 10<sup>9</sup></code></li> |
| 33 | +</ul> |
0 commit comments