Length of Longest Fibonacci Subsequence LeetCode solution in Java

1
class Solution {
2
  /*
3
   * dp[i][j] is the max length of fibbonacci series whose last two elements
4
   * are A[i] & A[j]
5
   * for any integer A[k] we need to find two number A[i] & A[j] such that
6
   * i < j < k and A[i] + A[j] == A[k], we can find such pairs in O(n) time
7
   * complexity.
8
   * if there exist i,j,k such that i < j < k and A[i] + A[j] == A[k] then
9
   * dp[k][j] = dp[i][j] + 1 (A[k], A[j] are last two elements of fibbonacc series)
10
   */
11
  public int lenLongestFibSubseq(int[] A) {
12
    int n = A.length;
13
    int[][] dp = new int[n][n];
14
    int result = 0;
15
    for (int k = 2; k < n; k++) {
16
      int i = 0, j = k - 1;
17
      while (i < j) {
18
        int sum = A[i] + A[j] - A[k];
19
        if (sum < 0) {
20
          i++;
21
        } else if (sum > 0) {
22
          j--;
23
        } else {
24
          // ith, jth kth element are fibbonaci sequence
25
          dp[j][k] = dp[i][j] + 1; // since numbers are unique
26
          result = Math.max(result, dp[j][k]);
27
          i++;
28
          j--;
29
        }
30
      }
31
    }
32
    return result + 2 >= 3 ? result + 2 : 0;
33
  }
34
}