How to Find the Length of Longest Fibonacci Subsequence using Br
- 时间:2020-09-18 17:01:02
- 分类:网络文摘
- 阅读:93 次
A sequence X_1, X_2, …, X_n is fibonacci-like if:
n >= 3
X_i + X_{i+1} = X_{i+2} for all i + 2 <= nGiven a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A. If one does not exist, return 0.
(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)
Example 1:
Input: [1,2,3,4,5,6,7,8]
Output: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].Example 2:
Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18].Note:
3 <= A.length <= 1000
1 <= A[0] < A[1] < … < A[A.length – 1] <= 10^9
(The time limit has been reduced by 50% for submissions in Java, C, and C++.)
Bruteforce Algorithm to Find the Longest Fibonacci Sequence
Given the A[i] constrains that the maximum number of A[i] is no more than 10^9 and the fact that the fibonacci grows exponentially, we know roughly that there are at most 43 elements in the Fibonacci subsequences.
We remember the numbers using a set. Then we can bruteforce the pairs in O(N^2), and iteratively extending the sequence using set.find in O(1) time. The overall complexity is O(N^2 LogM) where M is the maximum value of the A[i].
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public: int lenLongestFibSubseq(vector<int>& A) { int n = A.size(); if (n <= 2) return 0; unordered_set<int> S(A.begin(), A.end()); int ans = 0; for (int i = 0; i < n; ++ i) { for (int j = i + 1; j < n; ++ j) { int x = A[j], y = A[i] + A[j]; int len = 2; while (S.count(y)) { int z = x + y; x = y; y = z; ans = max(ans, ++len); } } } return ans >= 3 ? ans : 0; } }; |
class Solution { public: int lenLongestFibSubseq(vector<int>& A) { int n = A.size(); if (n <= 2) return 0; unordered_set<int> S(A.begin(), A.end()); int ans = 0; for (int i = 0; i < n; ++ i) { for (int j = i + 1; j < n; ++ j) { int x = A[j], y = A[i] + A[j]; int len = 2; while (S.count(y)) { int z = x + y; x = y; y = z; ans = max(ans, ++len); } } } return ans >= 3 ? ans : 0; } };
Finding the Longest Fibonacci Sequence using Dynamic Programming Algorithm
Let’s consider this problem in DP manner where we define dp[i][j] is the length of the Fibonacci subsequence that ends at A[i] and A[j]. Then we can deduce the previous number in the Fibonacci subsequence is A[j] – A[i].
Using a hash map to remember the index of the numbers, we can find out if the A[j]-A[i] is in the array. If it this in the array, and the index is smaller than i, then we know the dp[j][k] will be dp[i][j] plus 1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | class Solution { public: int lenLongestFibSubseq(vector<int>& A) { int n = A.size(); if (n <= 2) return 0; unordered_map<int, int> index; for (int i = 0; i < n; ++ i) { index[A[i]] = i; } int ans = 0; unordered_map<int, unordered_map<int, int>> dp; for (int k = 0; k < n; ++ k) { for (int j = 0; j < k; ++ j) { int prev = A[k] - A[j]; if (index.find(prev) != index.end()) { int i = index[prev]; if (i < j) { dp[j][k] = max(2, dp[i][j]) + 1; ans = max(ans, dp[j][k]); } } } } return ans >= 3 ? ans : 0; } }; |
class Solution { public: int lenLongestFibSubseq(vector<int>& A) { int n = A.size(); if (n <= 2) return 0; unordered_map<int, int> index; for (int i = 0; i < n; ++ i) { index[A[i]] = i; } int ans = 0; unordered_map<int, unordered_map<int, int>> dp; for (int k = 0; k < n; ++ k) { for (int j = 0; j < k; ++ j) { int prev = A[k] - A[j]; if (index.find(prev) != index.end()) { int i = index[prev]; if (i < j) { dp[j][k] = max(2, dp[i][j]) + 1; ans = max(ans, dp[j][k]); } } } } return ans >= 3 ? ans : 0; } };
Special case has to be dealt with when the answer is less than 3 – which would not form a valid Fibonacci sequence. The Dynamic Programming Algorithm runs at O(N^2) time and using O(N) space.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:The Exact Amount that You Must Spend on a Great Blog Is… How to Make Videos Search Engines Love 5 Thoughts For Investing In Your Freelancing Career In 2017 How YouTube Can Work in Tandem With Your Blog Essena O’Neill Quits Social Media Kate Winslet Criticizes Social Media, Parents Social Media Quizzes Could Put You At Risk For Hacking Freelancing from Anywhere: Tips for Living and Working Abroad 5 Tools for Busy Bloggers #FatGirlsCan Blogger’s Book Released in Paperback
- 评论列表
-
- 添加评论