Length of Longest Fibonacci Subsequence

Description

A sequence X_1, X_2, ..., X_n is fibonacci-like if:

• n >= 3
• X_i + X_{i+1} = X_{i+2} for all i + 2 <= n

Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A.  If one does not exist, return 0.

(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, 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: [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: [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].

 

Note:

• 3 <= A.length <= 1000
• 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
• (The time limit has been reduced by 50% for submissions in Java, C, and C++.)

Solution(javascript)

/*
 * @lc app=leetcode id=873 lang=javascript
 *
 * [873] Length of Longest Fibonacci Subsequence
 */

// @lc code=start
// /** 注意是严格递增的
//  * DP + binary search  O(n^2 * log(n))
//  * @param {number[]} A
//  * @return {number}
//  */
// const lenLongestFibSubseq = function (A) {
//   const search = (start, target) => {
//     let left = start
//     let right = A.length - 1
//     while (left <= right) {
//       const middle = Math.floor(left + (right - left) / 2)
//       if (A[middle] === target) {
//         return middle
//       } if (A[middle] < target) {
//         left = middle + 1
//       } else {
//         right = middle - 1
//       }
//     }
//     return -1
//   }
//   const memo = []
//   const aux = (a, b) => {
//     memo[a] = memo[a] || []
//     if (memo[a][b] !== undefined) {
//       return memo[a][b]
//     }
//     if (b >= A.length - 1) {
//       return 0
//     }
//     const c = search(b + 1, A[a] + A[b])
//     if (c === -1) {
//       return 0
//     }
//     memo[a][b] = aux(b, c) + 1
//     return memo[a][b]
//   }
//   let max = 0
//   for (let i = 0; i < A.length; i++) {
//     for (let j = i + 1; j < A.length; j++) {
//       max = Math.max(max, aux(i, j))
//     }
//   }
//   return max > 0 ? max + 2 : 0
// }

// /** 注意是严格递增的
//  * Top-down: DP + Map  O(n^2)
//  * @param {number[]} A
//  * @return {number}
//  */
// const lenLongestFibSubseq = function (A) {
//   const map = A.reduce((acc, num, index) => {
//     acc[num] = index
//     return acc
//   }, {})

//   const memo = []
//   const aux = (a, b) => {
//     memo[a] = memo[a] || []
//     if (memo[a][b] !== undefined) {
//       return memo[a][b]
//     }
//     if (b >= A.length - 1) {
//       return 0
//     }
//     const c = map[A[a] + A[b]]
//     if (c === undefined) {
//       return 0
//     }
//     memo[a][b] = aux(b, c) + 1
//     return memo[a][b]
//   }
//   let max = 0
//   for (let i = 0; i < A.length; i++) {
//     for (let j = i + 1; j < A.length; j++) {
//       max = Math.max(max, aux(i, j))
//     }
//   }
//   return max > 0 ? max + 2 : 0
// }

/*
 * @lc app=leetcode id=873 lang=javascript
 *
 * [873] Length of Longest Fibonacci Subsequence
 */

// @lc code=start
// /** 注意是严格递增的
//  * DP + binary search  O(n^2 * log(n))
//  * @param {number[]} A
//  * @return {number}
//  */
// const lenLongestFibSubseq = function (A) {
//   const search = (start, target) => {
//     let left = start
//     let right = A.length - 1
//     while (left <= right) {
//       const middle = Math.floor(left + (right - left) / 2)
//       if (A[middle] === target) {
//         return middle
//       } if (A[middle] < target) {
//         left = middle + 1
//       } else {
//         right = middle - 1
//       }
//     }
//     return -1
//   }
//   const memo = []
//   const aux = (a, b) => {
//     memo[a] = memo[a] || []
//     if (memo[a][b] !== undefined) {
//       return memo[a][b]
//     }
//     if (b >= A.length - 1) {
//       return 0
//     }
//     const c = search(b + 1, A[a] + A[b])
//     if (c === -1) {
//       return 0
//     }
//     memo[a][b] = aux(b, c) + 1
//     return memo[a][b]
//   }
//   let max = 0
//   for (let i = 0; i < A.length; i++) {
//     for (let j = i + 1; j < A.length; j++) {
//       max = Math.max(max, aux(i, j))
//     }
//   }
//   return max > 0 ? max + 2 : 0
// }

/** 注意是严格递增的
 * Bottom-up  O(n^2)
 * @param {number[]} A
 * @return {number}
 */
const lenLongestFibSubseq = function (A) {
  const map = A.reduce((acc, num, index) => {
    acc[num] = index
    return acc
  }, {})

  const memo = A.map(() => A.map(() => 0))
  let max = 0
  for (let i = 0; i < A.length; i++) {
    for (let j = i + 1; j < A.length; j++) {
      const a = A[i]
      const b = A[j]
      const index = map[b - a]
      if (index < i) {
        memo[i][j] = memo[index][i] + 1
      }
      max = Math.max(max, memo[i][j])
    }
  }
  return max > 0 ? max + 2 : 0
}
// @lc code=end