def memoizeLSS$($a$)$:

T $=\{\}$ # Initialize the memo table to empty dictionary

# Now populate the entries for the base case

n $=$ len$($a$)$

for j in range$(-1,$ n$)$:

T$[($n$,$ j$)]=0$ # i $=$ n and j

# Now fill out the table : figure out the two nested for loops

# It is important to also figure out the order in which you iterate the indices i and j

# Use the recurrence structure itself as a guide: see for instance that T$[($i$,$j$)]$ will depend on T$[($i$+1,$ j$)]$

# your code here

return T

def lssLength$($a$,$ i$,$ j$)$:

assert False, 'Redefining lssLength: You should not be calling this function from your memoization code'

def checkMemoTableHasEntries$($a$,$ T$)$:

for i in range$($len$($a$)+1)$:

for j in range$($i$)$:

assert $($i$,$ j$)$ in T$,$ f'entry for $\{($i$,$j$)\}$ not in memo table'

def checkMemoTableBaseCase$($a$,$ T$)$:

n $=$ len$($a$)$

for j in range$(-1,$ n$)$:

assert T$[($n$,$ j$)]==0,$ f'entry for $\{($n$,$j$)\}$ is not zero as expected'

print$(\text{'}--$ Test $1--\text{'})$

a$1=[1,4,2,-2,0,-1,2,3]$

print$($a$1)$

T$1=$ memoizeLSS$($a$1)$

checkMemoTableHasEntries$($a$1,$ T$1)$

checkMemoTableBaseCase$($a$1,$ T$1)$

assert T$1[(0,-1)]==4,$ f'Test $1$: Expected answer is $4.$ your code returns $\{$T$1[(0,-1)]\}\text{'}$

print$(\text{'}$Passed$\text{'})$

print$(\text{'}--$Test$2--\text{'})$

a$2=[1,2,3,4,0,1,-1,-2,-3,-4,5,-5,-6]$

print$($a$2)$

T$2=$ memoizeLSS$($a$2)$

checkMemoTableHasEntries$($a$2,$ T$2)$

checkMemoTableBaseCase$($a$2,$ T$2)$

assert T$2[(0,-1)]==8,$ f'Test $2$: Expected answer is $8.$ Your code returns $\{$T$2[(0,-1)]\}\text{'}$

print$(\text{'}--$Test$3--\text{'})$

a$3=[0,2,4,6,8,10,12]$

print$($a$3)$

T$3=$ memoizeLSS$($a$3)$

checkMemoTableHasEntries$($a$3,$ T$3)$

checkMemoTableBaseCase$($a$3,$ T$3)$

assert T$3[(0,-1)]==1,$ f'Test $3$: Expected answer is $1.$ Your code returns $\{$T$3[(0,-1)]\}\text{'}$

print$(\text{'}--$Test$4--\text{'})$

a$4=[4,8,7,5,3,2,5,6,7,1,3,-1,0,-2,-3,0,1,2,1,3,1,0,-1,2,4,5,0,2,-3,-9,-4,-2,-3,-1]$

print$($a$4)$

T$4=$ memoizeLSS$($a$4)$

checkMemoTableHasEntries$($a$4,$ T$4)$

checkMemoTableBaseCase$($a$4,$ T$4)$

assert T$4[(0,-1)]==14,$ f'Text $4$: Expected answer is $14.$ Your code returns $\{$T$4[(0,-1)]\}\text{'}$

print$(\text{'}$All tests passed $(7$ points$)\text{'})$ Problem $1$ : Longest Stable Subsequence

Consider a list of numbers $a_0,a_1,$cdots,$a_{n-1}.$ Our goal is to find the the longest stable subsequence: $a_{i_1},a_{i_2},$cdots,$a_{i_k}$ which is a sub$-$list of the original list

that selects elements at indices $i_1,i_2,$dots,$i_k$ from the original list such that

$a_{i_{j+1}}-1a_{i_j}{a}_{i_{j+1}}+1|a_{i_{j+1}}-a_{i_j}|1+-1k1,4,2,-2,0,-1,2,31,0,-11,2,2,34,31,2,2,3n{a}_0,$dots,$a_{n-1}(i,a_j)a_i,$dots,$a_{n-1}{a}_i{a}_{i_1}|a_{i_1}-a_j|10\mathrm{.}0in.i=n{a}_j{a}_i,$dots,$a_{n-1}|a-a_j|1a_j=a_j$ Part $2$: Memoize the Recurrence

Construct a memo table as a dictionary that maps from $(i,j)$ where $0in$ and LSSLength$(a,i,a_j)a_j=a[j]j0a_j=(n^2)-1jto$ the value LSSLength$(a,i,a_j)$ where $a_j=a[j]$

$ifj0$ else $a_j=$ None.

Your code should run $in$ worst case time $(n^2).$