I am working on a DP problem to find longest stable subsequence, and I'm currently stuck with recovering the solution.
Here is the problem statement
I have tried the below solution,
def computeLSS(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
for i in range(0, n + 1):
for j in range(-1, n + 1):
T[(i, j)] = 0
for i in range(n - 1, -1, -1):
for j in range(n - 1 , -1, -1):
aj = a[j] if 0 <= j < len(a) else None
if aj != None and abs(a[i] - aj) > 1:
T[(i, j)] = T[(i + 1, j)]
if aj == None or abs(a[i] - aj) <= 1:
T[(i, j)] = max(1 + T[(i + 1), i], T[(i + 1, j)])
for i in range(n-2, -1, -1):
T[(i, -1)] = max(T[(i+1, -1)], T[(i+1, 0)], T[(i, 0)], 0)
i = 0
j = -1
sol = []
while i < n and j < n:
if abs(T[(i, j)] - T[(i+1, j)]) > 1:
sol.append(a[i])
j = i
i = i + 1
return sol
But it fails for the below test cases,
a2 = [1, 2, 3, 4, 0, 1, -1, -2, -3, -4, 5, -5, -6]
print(a2)
sub2 = computeLSS(a2)
print(f'sub2 = {sub2}')
assert len(sub2) == 8
a3 = [0,2, 4, 6, 8, 10, 12]
print(a3)
sub3 = computeLSS(a3)
print(f'sub3 = {sub3}')
assert len(sub3) == 1
I would really appreciate if someone can help me with some pointers like what might be the problem with my recovery code?

Tactually mean?athe length of the longest subsequence which starts with this item and the index of the next item of this subseq. For the rightmost item this would always be length 1 and next index -1 (no next item). Then you go from right to left and for each current item you find the item to its right with the longest subseq where you can prepend the current item to the subseq.