Length of Longest Fibonacci Subsequence Solutions in C++

/// Source : https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/description/
/// Author : liuyubobobo
/// Time   : 2018-07-21

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


/// Brute Force iterate the first 2 elements in the fibonacci sequence
/// Since the number will grow exponentially, there will be at most 43 items to check
/// Time Complexity: O(n^2*log(maxA))
/// Space Complexity: O(A)
class Solution {

public:
    int lenLongestFibSubseq(vector<int>& A) {

        unordered_set<int> nums;
        for(int a: A)
            nums.insert(a);

        int res = 2;
        for(int i = 0 ; i < A.size() ; i ++)
            for(int j = i + 1; j < A.size() ; j ++){
                int len = 2;
                int a = A[i], b = A[j];
                while(true){
                    int next = a + b;
                    if(next > 1e9)
                        break;
                    if(nums.find(next) == nums.end())
                        break;

                    a = b, b = next, len ++;
                }
                res = max(res, len);
            }
        return res > 2 ? res : 0;
    }
};


int main() {

    vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7, 8};
    cout << Solution().lenLongestFibSubseq(nums1) << endl;
    // 5

    vector<int> nums2 = {1, 3, 7, 11, 12, 14, 18};
    cout << Solution().lenLongestFibSubseq(nums2) << endl;
    // 3

    vector<int> nums3 = {2, 4, 5, 6, 7, 8, 11, 13, 14, 15, 21, 22, 34};
    cout << Solution().lenLongestFibSubseq(nums3) << endl;
    // 5

    return 0;
}

/// Source : https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/description/
/// Author : liuyubobobo
/// Time   : 2018-07-21

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


/// Memory Search
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {

private:
    int n;
    unordered_map<int, int> num_index;

public:
    int lenLongestFibSubseq(vector<int>& A) {

        n = A.size();
        num_index.clear();
        for(int i = 0 ; i < A.size() ; i ++)
            num_index[A[i]] = i;

        vector<vector<int>> dp(n, vector<int>(n, -1));
        int res = 0;
        for(int i = 1; i < n; i ++)
            for(int j = i + 1; j < n ; j ++)
                res = max(res, getRes(A, i, j, dp));
        return res == 2 ? 0 : res;
    }

private:
    int getRes(const vector<int>& A, int a, int b, vector<vector<int>>& dp){

        if(dp[a][b] != -1)
            return dp[a][b];

        if(A[b] - A[a] < A[a] && num_index.find(A[b] - A[a]) != num_index.end())
            return dp[a][b] = 1 + getRes(A, num_index[A[b] - A[a]], a, dp);
        return 2;
    }
};


int main() {

    vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7, 8};
    cout << Solution().lenLongestFibSubseq(nums1) << endl;
    // 5

    vector<int> nums2 = {1, 3, 7, 11, 12, 14, 18};
    cout << Solution().lenLongestFibSubseq(nums2) << endl;
    // 3

    vector<int> nums3 = {2, 4, 5, 6, 7, 8, 11, 13, 14, 15, 21, 22, 34};
    cout << Solution().lenLongestFibSubseq(nums3) << endl;
    // 5

    return 0;
}

/// Source : https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/description/
/// Author : liuyubobobo
/// Time   : 2018-07-21
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {

public:
    int lenLongestFibSubseq(vector<int>& A) {

        int n = A.size();
        unordered_map<int, int> num_index;
        for(int i = 0 ; i < A.size() ; i ++)
            num_index[A[i]] = i;

        vector<vector<int>> dp(n, vector<int>(n, 2));
        int res = 0;

        for(int j = 2; j < n ; j ++)
            if(A[0] + A[1] == A[j]){
                dp[1][j] = 3;
                res = max(res, 3);
            }

        for(int i = 2; i < n ; i ++)
            for(int j = i + 1; j < n ; j ++){
                if(A[j] - A[i] < A[i] && num_index.find(A[j] - A[i]) != num_index.end()) {
                    dp[i][j] = dp[num_index[A[j] - A[i]]][i] + 1;
                    res = max(res, dp[i][j]);
                }
            }
        return res;
    }
};


int main() {

    vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7, 8};
    cout << Solution().lenLongestFibSubseq(nums1) << endl;
    // 5

    vector<int> nums2 = {1, 3, 7, 11, 12, 14, 18};
    cout << Solution().lenLongestFibSubseq(nums2) << endl;
    // 3

    vector<int> nums3 = {2, 4, 5, 6, 7, 8, 11, 13, 14, 15, 21, 22, 34};
    cout << Solution().lenLongestFibSubseq(nums3) << endl;
    // 5

    return 0;
}