Array
Hash Table
Dynamic Programming
Description
A sequence x1 , x2 , ..., xn
is Fibonacci-like if:
n >= 3
xi + xi+1 == xi+2
for all i + 2 <= n
Given a strictly increasing array arr
of positive integers forming a sequence, return the length of the longest Fibonacci-like subsequence of arr
. If one does not exist, return 0
.
A subsequence is derived from another sequence arr
by deleting any number of elements (including none) from arr
, without changing the order of the remaining elements. For example, [3, 5, 8]
is a subsequence of [3, 4, 5, 6, 7, 8]
.
Example 1:
Input: arr = [1,2,3,4,5,6,7,8]
Output: 5
Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8].
Example 2:
Input: arr = [1,3,7,11,12,14,18]
Output: 3
Explanation : The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].
Constraints:
3 <= arr.length <= 1000
1 <= arr[i] < arr[i + 1] <= 109
Solutions
Solution 1
Python3 Java C++ Go JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution :
def lenLongestFibSubseq ( self , arr : List [ int ]) -> int :
mp = { v : i for i , v in enumerate ( arr )}
n = len ( arr )
dp = [[ 0 ] * n for _ in range ( n )]
for i in range ( n ):
for j in range ( i ):
dp [ j ][ i ] = 2
ans = 0
for i in range ( n ):
for j in range ( i ):
d = arr [ i ] - arr [ j ]
if d in mp and ( k := mp [ d ]) < j :
dp [ j ][ i ] = max ( dp [ j ][ i ], dp [ k ][ j ] + 1 )
ans = max ( ans , dp [ j ][ i ])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 class Solution {
public int lenLongestFibSubseq ( int [] arr ) {
int n = arr . length ;
Map < Integer , Integer > mp = new HashMap <> ();
for ( int i = 0 ; i < n ; ++ i ) {
mp . put ( arr [ i ] , i );
}
int [][] dp = new int [ n ][ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < i ; ++ j ) {
dp [ j ][ i ] = 2 ;
}
}
int ans = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < i ; ++ j ) {
int d = arr [ i ] - arr [ j ] ;
if ( mp . containsKey ( d )) {
int k = mp . get ( d );
if ( k < j ) {
dp [ j ][ i ] = Math . max ( dp [ j ][ i ] , dp [ k ][ j ] + 1 );
ans = Math . max ( ans , dp [ j ][ i ] );
}
}
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 class Solution {
public :
int lenLongestFibSubseq ( vector < int >& arr ) {
unordered_map < int , int > mp ;
int n = arr . size ();
for ( int i = 0 ; i < n ; ++ i ) mp [ arr [ i ]] = i ;
vector < vector < int >> dp ( n , vector < int > ( n ));
for ( int i = 0 ; i < n ; ++ i )
for ( int j = 0 ; j < i ; ++ j )
dp [ j ][ i ] = 2 ;
int ans = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < i ; ++ j ) {
int d = arr [ i ] - arr [ j ];
if ( mp . count ( d )) {
int k = mp [ d ];
if ( k < j ) {
dp [ j ][ i ] = max ( dp [ j ][ i ], dp [ k ][ j ] + 1 );
ans = max ( ans , dp [ j ][ i ]);
}
}
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 func lenLongestFibSubseq ( arr [] int ) int {
n := len ( arr )
mp := make ( map [ int ] int , n )
for i , v := range arr {
mp [ v ] = i + 1
}
dp := make ([][] int , n )
for i := 0 ; i < n ; i ++ {
dp [ i ] = make ([] int , n )
for j := 0 ; j < i ; j ++ {
dp [ j ][ i ] = 2
}
}
ans := 0
for i := 0 ; i < n ; i ++ {
for j := 0 ; j < i ; j ++ {
d := arr [ i ] - arr [ j ]
k := mp [ d ] - 1
if k >= 0 && k < j {
dp [ j ][ i ] = max ( dp [ j ][ i ], dp [ k ][ j ] + 1 )
ans = max ( ans , dp [ j ][ i ])
}
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 /**
* @param {number[]} arr
* @return {number}
*/
var lenLongestFibSubseq = function ( arr ) {
const mp = new Map ();
const n = arr . length ;
const dp = new Array ( n ). fill ( 0 ). map (() => new Array ( n ). fill ( 0 ));
for ( let i = 0 ; i < n ; ++ i ) {
mp . set ( arr [ i ], i );
for ( let j = 0 ; j < i ; ++ j ) {
dp [ j ][ i ] = 2 ;
}
}
let ans = 0 ;
for ( let i = 0 ; i < n ; ++ i ) {
for ( let j = 0 ; j < i ; ++ j ) {
const d = arr [ i ] - arr [ j ];
if ( mp . has ( d )) {
const k = mp . get ( d );
if ( k < j ) {
dp [ j ][ i ] = Math . max ( dp [ j ][ i ], dp [ k ][ j ] + 1 );
ans = Math . max ( ans , dp [ j ][ i ]);
}
}
}
}
return ans ;
};
GitHub