Python O(n^2) Solution With Comments


#1
class Subject:
    def __init__(self, input):
        # input list
        self.input = input
        # size of input array
        self.input_length = len(input)
        # a dictionary containing solutions for index i, if the sequence 
        # starts with A[i]
        self.mem = {i: 0 for i in range(self.input_length)}
        self.max_length = 0


class Solution:
    # @param A : tuple of integers
    # @return an integer
    def lis(self, A):
        length = len(A)
        if length <= 1:
            return length
        return self._lis(Subject(A), 0)

    def _lis(self, subject, start_index):
        # a non-zero value means we have already found the solution 
        # if the sequence starts from this 
        if subject.mem[start_index] > 0:
            return

        # start from the very last element 
        for i in reversed(range(start_index, subject.input_length)):
            j = i + 1
            # this finds out the longest sequence after index i, if A[i] is selected
            max_after_i = 0
            while j < subject.input_length:
                if subject.input[j] <= subject.input[i]:
                    j += 1
                    continue
                # a non-zero value means we have already found the solution 
                # if the sequence starts from this index
                if subject.mem[start_index] == 0:
                    self._lis(subject, j)
                # is the sequence generated from j the longest?
                if subject.mem[j] > max_after_i:
                    max_after_i = subject.mem[j]
                j += 1
            # add 1 because of A[i] to the macimum available sequence after 
            # selection of A[i]
            subject.mem[i] = 1 + max_after_i
            # do we have a new maximum?
            if subject.mem[i] > subject.max_length:
                subject.max_length = subject.mem[i]

        return subject.max_length

#2

Reviewing my answer after a couple of months, I’m like what the hell were you thinking???