Untitled

"""

"""

def longest_decreasing_subsequence(l: list):
    n = len(l)
    if n == 0:
        return []   # obvious

    dp = [1] * n            # store length of longest decreasing subsequence
    predecessors = [-1] * n # store predecessor index

    for i in range(1, n):
        for j in range(i):
            if l[j] > l[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1       # store len of subsequence for each idx
                predecessors[i] = j     # store predecessor

    max_len = max(dp)
    max_idx = dp.index(max_len)

    res = []        # reconstruct result
    while max_idx != -1:
        res.append(l[max_idx])
        max_idx = predecessors[max_idx]

    res.reverse()   # result is reversed

    print(f'dp: {dp}')
    print(f'predecessors: {predecessors}')

    return res

l = [9, 4, 3, 6, 2, 8, 1]
subseq = longest_decreasing_subsequence(l)
print("Res:", subseq)