Untitled
unknown
plain_text
5 months ago
901 B
3
Indexable
""" """ 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)
Editor is loading...
Leave a Comment