cassidoo_problem_09142020.py

'''
Given an array of increasing integers, find the length of the longest fibonacci-like subsequence of the array. If one does not exist, return 0. A sequence is “fibonacci-like” if X_i + X_{i+1} = X_{i+2}.
'''

def fibonacci_like(a):
    '''
    solution: O(n^3-ish)
    me: 🤡
    '''
    max_fib_len = 0

    for fib_1_index in range(len(a) - 1):
        for fib_2_index in range(fib_1_index + 1, len(a)):
            fib_len = 0
            while fib_2_index < len(a):
                fib_1 = a[fib_1_index]
                fib_2 = a[fib_2_index]
                fib_sum = fib_1 + fib_2
                if fib_sum in a[fib_2_index:]:
                    # Found another element in the sequence!
                    fib_len += 1
                    fib_1_index, fib_2_index = fib_2_index, a.index(fib_sum)
                else:
                    # Reached the end of the sequence, count the length
                    fib_2_index += 1
            if fib_len != 0:
                fib_len += 2
            max_fib_len = max(fib_len, max_fib_len)

    return max_fib_len

if __name__ == "__main__":
    assert fibonacci_like([1,3,7,11,12,14,18]) == 3
    assert fibonacci_like([9,10,11]) == 0
    assert fibonacci_like([9,10,19,25,29]) == 4
    assert fibonacci_like([]) == 0