0

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

enter image description here

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?

3
  • What should the keys and values of T actually mean? Commented Nov 6, 2023 at 0:37
  • In the above code, T stores the length of the subarray for given index i and previous index j. i is the current element in array a, and j is the previous element. Commented Nov 6, 2023 at 2:33
  • This seems unnecessarily complicated to me. You could just store for each item in a the 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. Commented Nov 6, 2023 at 9:56

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.