Leetcode 905 Solution

This article provides solution to leetcode question 905 (length-of-longest-fibonacci-subsequence)
Categories:
Tags:
Access this page by simply typing in "lcs 905" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/length-of-longest-fibonacci-subsequence

Solution

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& A) {
        vector<vector<bool>> dp(A.size(), vector<bool>(A.size(), false));
        map<int, int> nums;
        int maxlen = 0;

        for (int i = 0; i < A.size(); i++)
            nums[A[i]] = i;

        for (int i = 0; i < A.size(); i++)
        {
            for (int j = i + 1; j < A.size(); j++)
            {
                int i1 = i;
                int i2 = j;
                int len = 2;

                if (dp[i1][i2])
                    continue;

                while (true)
                {
                    dp[i1][i2] = true;

                    int num1 = A[i1];
                    int num2 = A[i2];
                    int num3 = num1 + num2;

                    if (nums.find(num3) == nums.end())
                        break;

                    int i3 = nums[num3];
                    i1 = i2;
                    i2 = i3;
                    len++;
                }

                maxlen = max(len, maxlen);
            }
        }

        return maxlen == 2 ? 0 : maxlen;
    }
};