873. Length of Longest Fibonacci Subsequence

Version #1 Naiive DP

Optimized
Since A[A[j] - A[i]]   ---   A[i]   ----  A [j]
Give a pair of A[i] A[j] there's only 1 A[j] - [i] -> So we can update dp[i][j] directly instead of calculate the max
81.27 %
class Solution {
    public int lenLongestFibSubseq(int[] A) {
int len = A.length;
Map<Integer, Integer> map = new HashMap<>();
int max = 0;
// dp[i][j] longest fib end with i and j
int[][] dp = new int[len][len];
for (int j = 0; j < len; j++) {
            map.put(A[j], j);
for (int i = j - 1; i >= 0; i--) {
if (A[j] - A[i] < A[i] && map.containsKey(A[j] - A[i])) {
dp[i][j] = 1 + dp[map.get(A[j] - A[i])][i];
}
// System.out.println(A[i] + "," + A[j] + " -> " + dp[i][j]);
max = Math.max(max, dp[i][j]);
}
}
return max == 0 ? 0 : (max + 2);
}
}



52.72 %
1 Corner Case -> 1 2 -> if we don't check A[j]-A[i] < A[i] -> this case will return length of 1
However it is not
Given it is a strictly increasing array, we can guarantee that there's no duplicates, so we can use a hashmap to map the position of number and its index

class Solution {
    public int lenLongestFibSubseq(int[] A) {
int len = A.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) map.put(A[i], i);
int max = 0;
// dp[i][j] longest fib end with i and j
int[][] dp = new int[len][len];
for (int j = 1; j < len; j++) {
for (int i = j - 1; i >= 0; i--) {
if (A[j] - A[i] < A[i] && map.containsKey(A[j] - A[i])) {
dp[i][j] = Math.max(dp[i][j], 1 + dp[map.get(A[j] - A[i])][i]);
}
// System.out.println(A[i] + "," + A[j] + " -> " + dp[i][j]);
max = Math.max(max, dp[i][j]);
}
}
return max == 0 ? 0 : (max + 2);
}
}