 # 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???