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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/**
 * Find the length of the longest subsequence that forms a Fibonacci sequence.
 * Dynamic Programming with Hash Map approach.
 * 
 * @param {number[]} arr - The input array
 * @return {number} - The length of the longest Fibonacci subsequence
 */
function lenLongestFibSubseq(arr) {
  const n = arr.length;
  
  // Create a hash map for quick lookup
  const index = new Map();
  for (let i = 0; i < n; i++) {
    index.set(arr[i], i);
  }
  
  // Initialize DP table
  const dp = Array(n).fill().map(() => Array(n).fill(0));
  
  let maxLength = 0;
  
  for (let j = 0; j < n; j++) {
    for (let i = 0; i < j; i++) {
      // Compute the previous element in the Fibonacci sequence
      const prev = arr[j] - arr[i];
      
      // Check if prev exists and is smaller than arr[i]
      if (prev < arr[i] && index.has(prev)) {
        const k = index.get(prev);
        
        // Update DP table
        dp[i][j] = dp[k][i] > 0 ? dp[k][i] + 1 : 3;
        
        // Update maxLength
        maxLength = Math.max(maxLength, dp[i][j]);
      }
    }
  }
  
  return maxLength;
}
 
/**
 * Find the length of the longest subsequence that forms a Fibonacci sequence.
 * Optimized Dynamic Programming approach.
 * 
 * @param {number[]} arr - The input array
 * @return {number} - The length of the longest Fibonacci subsequence
 */
function lenLongestFibSubseqOptimized(arr) {
  const n = arr.length;
  
  // Create a hash map for quick lookup
  const index = new Map();
  for (let i = 0; i < n; i++) {
    index.set(arr[i], i);
  }
  
  // Initialize DP hash map
  const dp = new Map();
  
  let maxLength = 0;
  
  for (let j = 0; j < n; j++) {
    for (let i = 0; i < j; i++) {
      // Compute the previous element in the Fibonacci sequence
      const prev = arr[j] - arr[i];
      
      // Check if prev exists and is smaller than arr[i]
      if (prev < arr[i] && index.has(prev)) {
        const k = index.get(prev);
        
        // Create keys for the DP hash map
        const key1 = k * n + i;
        const key2 = i * n + j;
        
        // Update DP hash map
        dp.set(key2, dp.has(key1) ? dp.get(key1) + 1 : 3);
        
        // Update maxLength
        maxLength = Math.max(maxLength, dp.get(key2));
      }
    }
  }
  
  return maxLength;
}
 
/**
 * Find the length of the longest subsequence that forms a Fibonacci sequence.
 * Brute Force approach.
 * 
 * @param {number[]} arr - The input array
 * @return {number} - The length of the longest Fibonacci subsequence
 */
function lenLongestFibSubseqBruteForce(arr) {
  const n = arr.length;
  
  // Create a hash set for quick lookup
  const set = new Set(arr);
  
  let maxLength = 0;
  
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      let a = arr[i];
      let b = arr[j];
      let length = 2;
      
      // Try to extend the Fibonacci sequence
      while (set.has(a + b)) {
        const next = a + b;
        a = b;
        b = next;
        length++;
      }
      
      // Update maxLength if we found a Fibonacci sequence of length at least 3
      if (length >= 3) {
        maxLength = Math.max(maxLength, length);
      }
    }
  }
  
  return maxLength;
}
 
// Test cases
console.log(lenLongestFibSubseq([1, 2, 3, 4, 5, 6, 7, 8]));  // 5
console.log(lenLongestFibSubseq([1, 3, 7, 11, 12, 14, 18]));  // 3
console.log(lenLongestFibSubseq([1, 2, 4, 8, 16]));  // 0
 
console.log(lenLongestFibSubseqOptimized([1, 2, 3, 4, 5, 6, 7, 8]));  // 5
console.log(lenLongestFibSubseqOptimized([1, 3, 7, 11, 12, 14, 18]));  // 3
console.log(lenLongestFibSubseqOptimized([1, 2, 4, 8, 16]));  // 0
 
console.log(lenLongestFibSubseqBruteForce([1, 2, 3, 4, 5, 6, 7, 8]));  // 5
console.log(lenLongestFibSubseqBruteForce([1, 3, 7, 11, 12, 14, 18]));  // 3
console.log(lenLongestFibSubseqBruteForce([1, 2, 4, 8, 16]));  // 0