LeetCode Solutions
class Solution {
public:
int lenLongestFibSubseq(vector<int>& A) {
const int n = A.size();
int ans = 0;
vector<vector<int>> dp(n, vector<int>(n, 2));
unordered_map<int, int> numToIndex;
for (int i = 0; i < n; ++i)
numToIndex[A[i]] = i;
for (int j = 0; j < n; ++j)
for (int k = j + 1; k < n; ++k) {
const int ai = A[k] - A[j];
if (ai < A[j] && numToIndex.count(ai)) {
const int i = numToIndex[ai];
dp[j][k] = dp[i][j] + 1;
ans = max(ans, dp[j][k]);
}
}
return ans;
}
};
|
class Solution {
public int lenLongestFibSubseq(int[] A) {
final int n = A.length;
int ans = 0;
int[][] dp = new int[n][n];
Arrays.stream(dp).forEach(row -> Arrays.fill(row, 2));
Map<Integer, Integer> numToIndex = new HashMap<>();
for (int i = 0; i < n; ++i)
numToIndex.put(A[i], i);
for (int j = 0; j < n; ++j)
for (int k = j + 1; k < n; ++k) {
final int ai = A[k] - A[j];
if (ai < A[j] && numToIndex.containsKey(ai)) {
final int i = numToIndex.get(ai);
dp[j][k] = dp[i][j] + 1;
ans = Math.max(ans, dp[j][k]);
}
}
return ans;
}
}
|
class Solution:
def lenLongestFibSubseq(self, A: List[int]) -> int:
n = len(A)
ans = 0
numToIndex = {a: i for i, a in enumerate(A)}
dp = [[2] * n for _ in range(n)]
for j in range(n):
for k in range(j + 1, n):
ai = A[k] - A[j]
if ai < A[j] and ai in numToIndex:
i = numToIndex[ai]
dp[j][k] = dp[i][j] + 1
ans = max(ans, dp[j][k])
return ans
|
