Leetcode 873. Length of Longest Fibonacci Subsequence

문제

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].

x1, x2, ..., xn으로 이루어진 수열이 피보나치 유사 수열(Fibonacci-like sequence)이라고 할 때, 다음 조건을 만족해야 합니다:

• n >= 3
• 모든 i + 2 <= n에 대해 xi + xi+1 == xi+2

양의 정수로 이루어진 엄격히 증가하는 배열 arr이 주어졌을 때, 이 배열에서 추출한 가장 긴 피보나치 유사 부분수열의 길이를 반환하세요. 만약 그러한 부분수열이 존재하지 않으면 0을 반환하세요.

부분수열(subsequence)은 배열 arr에서 임의의 개수의 요소(0개 포함)를 삭제하여 얻어지는 수열로, 남은 요소의 순서를 변경하지 않습니다. 예를 들어, [3, 5, 8]은 [3, 4, 5, 6, 7, 8]의 부분수열입니다.

---

예시

입력: arr = [1,2,3,4,5,6,7,8]
출력: 5
설명: 가장 긴 피보나치 유사 부분수열은 [1,2,3,5,8]입니다.

---

제한

• $3 <= arr.length <= 1000$
• $1 <= arr[i] < arr[i + 1] <= 10^9$

---

풀이

• 그냥 브루트포스하게 풀면 된다.

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        N = len(arr)
        aset = set(arr)

        ans = 0

        for i in range(N - 1):
            for j in range(i + 1, N):
                first, second = arr[i], arr[j]
                res = 2

                while first + second in aset:
                    first, second = second, first + second
                    res += 1
                    ans = max(ans, res)

        return ans

진짜임