Solutions for longest increasing subsequence

    • @TerryDic
    • @Robert, submitted in Python 2, achived 100% score
    cache = None
    
    
    def get_subseq(arr, start):
        if start == len(arr):
            return 0
    
        current = arr[start]
        max_inc = 1
        for index in range(start + 1, len(arr)):
            if arr[index] >= current:
                if index in cache:
                    count = cache[index]
                else:
                    count = get_subseq(arr, index) + 1
                    cache[index] = count
                if count > max_inc:
                    max_inc = count
    
        return max_inc
    
    
    def solve(arr):
        global cache
        cache = dict()
        return get_subseq(arr, 0)
    • @TerryDic
    • @Robert, submitted in Python 3, achived 100% score
    cache = None
    
    
    def get_subseq(arr, start):
        if start == len(arr):
            return 0
    
        current = arr[start]
        max_inc = 1
        for index in range(start + 1, len(arr)):
            if arr[index] >= current:
                if index in cache:
                    count = cache[index]
                else:
                    count = get_subseq(arr, index) + 1
                    cache[index] = count
                if count > max_inc:
                    max_inc = count
    
        return max_inc
    
    
    def solve(arr):
        global cache
        cache = dict()
        return get_subseq(arr, 0)