[LeetCode] 873. Length of Longest Fibonacci Subsequence

Problem

https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/description/

Leetcode - Length of Longest Fibonacci Subsequence

Type - Dynamic programming

Difficulty - Medium

Approach & Solution

Let DP[prev][curr] is the length of Fibonacci-like subsequence which ends with index prev and curr of array.

With two-pointer approach, we can find the pair <i, j> such that arr[i] + arr[j] = arr[k] {for (0 <= i < j < k < n)}.

If the pair matches, dp[j][k] = dp[i][j]+1.

It means append arr[k] to the subsequence.

data structures & variables:

• dp[prev][curr]: length of Fibonacci-like subsequence which has postfix with arr[prev], arr[curr].

• ans: longest length\

With iterating curr from 2 to n-1:

• Initialize start = 0, end = curr -1.

• If arr[start] + arr[end] > arr[curr], decrement end by 1 since sum is larger.

• Else if arr[start] + arr[end] < arr[curr], increment start by 1 since sum is smaller.

• Else(arr[start] + arr[end] == arr[curr]), update dp[curr][end] = dp[start][end] + 1

  • Update ans to largest.

  • Reduce boundary for both side(start++, end—)

If ans = 0, return 0 since there’s no such subsequences.

Else, in dp matrix, we didn’t considered prefix two numbers.

So return ans+2.

Complexity

Time Complexity: O(n²) - Traverse array with two pointer for n times

Space Complexity: O(n²) - DP Matrix.

Code (C++ | Go)

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();

        // dp[prev][curr] = length of fivo seq;
        vector<vector<int>> dp(n, vector<int>(n, 0));
        int ans = 0;

        for(int curr = 2; curr < n; curr++) {
            int start = 0;
            int end = curr-1;
            while(start < end) {
                int sum = arr[start] + arr[end];
                if(sum > arr[curr]) {
                    end--;
                } else if(sum < arr[curr]) {
                    start++;
                } else {
                    dp[end][curr] = dp[start][end]+1;
                    ans = max(ans, dp[end][curr]);
                    end--;
                    start++;
                }
            }
        }

        ans += 2;
        return ans < 3? 0 : ans;
    }
};

func lenLongestFibSubseq(arr []int) int {
    n := len(arr)
    ans := 0
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
        for j := 0; j < n; j++ {
            dp[i][j] = 0
        }
    }

    for curr := 2; curr < n; curr++ {
        start := 0
        end := curr-1
        for start < end {
            sum := arr[start] + arr[end]
            if sum > arr[curr] {
                end--
            } else if sum < arr[curr] {
                start++
            } else {
                dp[end][curr] = dp[start][end] + 1
                ans = max(ans, dp[end][curr])
                end--
                start++
            }
        }
    }
    if ans == 0 {
        return 0
    }
    return ans+2
}