JavaScript를 사용하여 배열에서 피보나치 수열 찾기

피보나치 수열:

시퀀스 X_1, X_2, ..., X_n은 다음과 같은 경우 피보나치입니다.

• n>=3

• X_i + X_{i+1} =모든 i + 2 <=n

  에 대해 X_{i+2}

문제

첫 번째이자 유일한 인수로 숫자 배열 arr을 취하는 JavaScript 함수를 작성해야 합니다. 우리 함수는 배열 arr에 존재하는 가장 긴 피보나치 부분 수열의 길이를 찾아 반환해야 합니다.

하위 시퀀스는 나머지 요소의 순서를 변경하지 않고 arr에서 요소 수(없음 포함)를 삭제하여 다른 시퀀스 arr에서 파생됩니다.

예를 들어 함수에 대한 입력이

입력

const arr = [1, 3, 7, 11, 14, 25, 39];

출력

const output = 5;

출력 설명

가장 긴 피보나치 부분 수열은 [3, 11, 14, 25, 39]

다음은 코드입니다:

예시

const arr = [1, 3, 7, 11, 14, 25, 39];
const longestFibonacci = (arr = []) => {
   const map = arr.reduce((acc, num, index) => {
      acc[num] = index
      return acc
   }, {})
   const memo = arr.map(() => arr.map(() => 0))
   let max = 0
   for(let i = 0; i < arr.length; i++) {
      for(let j = i + 1; j < arr.length; j++) {
         const a = arr[i]
         const b = arr[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
};
console.log(longestFibonacci(arr));

출력

5