[LeetCode]Length of Longest Fibonacci Subsequence

斐波那契数列由前两项决定，所以我们遍历前两项的所有可能，然后去题目给的数字里验证最长的数列是多少。前两项总共的组合有O(N ^ 2)个，对于斐波那契数列，f(n) > 2 * f(n - 2)是必定成立的，数列每隔两项就至少会翻一倍。所以最长的序列也就2 * log M，M为数组的最大值。时间复杂度O(N^2 * log M)，空间复杂度O(n)，用hash set存，代码如下：

	class Solution {
	public:
	int lenLongestFibSubseq(vector<int>& A) {
	int len = A.size(), res = 0;
	unordered_set<int> set;
	for (const auto& num : A)
	set.insert(num);
	for (int i = 0; i < len; ++i)
	for (int j = i + 1; j < len; ++j)
	res = max(res, FibLen(set, A[i], A[j]));
	return res;
	}
	private:
	int FibLen(unordered_set<int>& set, int f1, int f2)
	{
	int len = 2;
	while (true)
	{
	int f3 = f1 + f2;
	if (set.find(f3) == set.end())break;
	++len;
	f1 = f2;
	f2 = f3;
	}
	return len >= 3 ? len : 0;
	}
	};

view raw Length of Longest Fibonacci Subsequence.cpp hosted with ❤ by GitHub

既然数列可以由前两项决定，那当然也可以由后两项决定，那么我们就可以参考LIS的的思路。DP[i][j]代表以A[i], A[j]两项结尾的数列，对于每个j，我们遍历之前的所有i，如果输入数组中存在k = A[i] - A[j] && k < A[j]，我们更新dp[A[i]][A[j]] = max(dp[A[i]][A[j]], dp[k][A[i]] + 1)。时间复杂度O(n ^ 2)，空间复杂度O(n^2)，代码如下：

	class Solution {
	public:
	int lenLongestFibSubseq(vector<int>& A) {
	int len = A.size(), res = 0;
	unordered_map<int, int> map;
	for (int i = 0; i < len; ++i)map[A[i]] = i;
	//longest fib len for seq ends at ..., A[i], A[j]
	//compress i j to i * len + j, otherwise TLE
	unordered_map<int, int> dp;
	for (int i = 0; i < len; ++i)
	{
	for (int j = 0; j < i; ++j)
	{
	//don't set dp[key] = 2 before this line, otherwise we will have MLE
	if (A[i] - A[j] >= A[j] || map.find(A[i] - A[j]) == map.end())continue;
	int key = j * len + i;
	int k = map[A[i] - A[j]];
	dp[key] = max(dp[key], 1 + (dp[k * len + j]? dp[k * len + j]: 2));//set here to save space
	res = max(res, dp[key]);
	}
	}
	return res >= 3 ? res : 0;
	}
	};

view raw Length of Longest Fibonacci Subsequence_2.cpp hosted with ❤ by GitHub