피보나치 수열:
시퀀스 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