function to calculate Longest Increasing Subsequence given an array of unsorted integers

longest_increasing_subsequence.py

def find_k(arr_i, l ,r, ends):
    # ends here is a sorted array.
    # binary search
    while r - l > 1:
        m = (l+r)//2
        if arr_i <= ends[m]: r = m
        else: l = m
    
    return r
    
    # linear search (for understanding)
    # for i in range(1, n-1):
    #     if arr_i <= ends[i+1]:
    #         return i + 1

def longestIncreasingSubsequence(arr):

    n = len(arr)
    
    # O(nlogn) solution

    lis_len = 0
    end_elements = [-1 for i in range(n+1)]

    for i in range(n):
      
        # if arr[i] is min of all end elements
            # start new list with arr[i]
        # if arr[i] is max of all end elements
            # extend longest list with arr[i]
        # if arr[i] is somewhere in middle 
            # search for k where end_elements[k] < arr[i] < end_elements[k+1]

        if arr[i] < end_elements[1]:
            end_elements[1] = arr[i]
        elif arr[i] > end_elements[lis_len]:
            lis_len += 1
            end_elements[lis_len] = arr[i]
        else:
            k = find_k(arr[i], 1, lis_len+1, end_elements)
            end_elements[k] = arr[i]
    
    print(end_elements)
    return lis_len
        
    # O(n^2) solution 

    lis = [1 for i in arr]

    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]:
                lis[i] = max(lis[i], 1 + lis[j])
    
    print(lis)
    return lis[n-1]