Problem
A sequence X_1, X_2, ..., X_n is fibonacci-like if:
n >= 3X_i + X_{i+1} = X_{i+2}for alli + 2 <= n
Given 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 <= 10001 <= 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++.)
Solution 1: DP
C++
|
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 27 28 |
// Author: Huahua // Running time: 68 ms // // w/ Hashtable // Time complexity: O(n^2) // Space complexity: O(n^2) class Solution { public: int lenLongestFibSubseq(vector<int>& A) { const int n = A.size(); unordered_map<int, int> m; for (int i = 0; i < n; ++i) m[A[i]] = i; vector<vector<int>> dp(n, vector<int>(n, 2)); int ans = 0; for (int j = 0; j < n; ++j) for (int k = j + 1; k < n; ++k) { int a_i = A[k] - A[j]; if (a_i >= A[j]) break; // pruning 168 ms -> 68 ms auto it = m.find(a_i); if (it == end(m)) continue; int i = it->second; dp[j][k] = dp[i][j] + 1; ans = max(ans, dp[j][k]); } return ans; } }; |
C++ V2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 96 ms // w / Binary Search // Time complexity: O(n^2logn) // Space complexity: O(n) class Solution { public: int lenLongestFibSubseq(vector<int>& A) { const int n = A.size(); vector<vector<int>> dp(n, vector<int>(n, 2)); int ans = 0; for (int j = 0; j < n; ++j) for (int k = j + 1; k < n; ++k) { int a_i = A[k] - A[j]; if (a_i >= A[j]) break; auto it = lower_bound(begin(A), begin(A) + j, a_i); int i = it - begin(A); if (A[i] != a_i) continue; dp[j][k] = dp[i][j] + 1; ans = max(ans, dp[j][k]); } return ans; } }; |
Solution 2: HashTable
Time complexity: O(n^3)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 172 ms class Solution { public: int lenLongestFibSubseq(vector<int>& A) { const int n = A.size(); unordered_set<int> m(begin(A), end(A)); int ans = 0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) { int a = A[i]; int b = A[j]; int c = a + b; int l = 2; while (m.count(c)) { a = b; b = c; c = a + b; ans = max(ans, ++l); } } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
[…] Reference:http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-873-length-of-longest-fibonacci-subseque… […]