The code below is given a sequence of positive integers to find the longest increasing and the longest decreasing subsequence of the sequence. write the algorithm for the python code below. def prints(arr): for x in arr: print(x, end=" ") print() def constructPrintLDS(arr, n): l = [[] for i in range(n)] l[0].append(arr[0]) for i in range(1, n): for j in range(i): if arr[i] < arr[j] and (len(l[i]) < len(l[j]) + 1): l[i] = l[j].copy() l[i].append(arr[i]) maxx = l[0] for x in l: if len(x) > len(maxx): maxx = x prints(maxx) def constructPrintLIS(arr, n): l = [[] for i in range(n)] l[0].append(arr[0]) for i in range(1, n): for j in range(i): if arr[i] > arr[j] and (len(l[i]) < len (l[j]) + 1): l[i] = l[j].copy() l[i].append(arr[i]) maxx = l[0] for x in l: if len(x) > len(maxx): maxx = x prints(maxx) if __name__ == "__main__": arr = list(map(int, input("Enter your input array space separated: ").split())) n = len(arr) print("The Longest increasing Subsequence: ") constructPrintLIS(arr, n) print("The Longest decreasing Subsequence: ") constructPrintLDS(arr, n)
The code below is given a sequence of positive integers to find the longest increasing and the longest decreasing subsequence of the sequence. write the
def prints(arr):
for x in arr:
print(x, end=" ")
print()
def constructPrintLDS(arr, n):
l = [[] for i in range(n)]
l[0].append(arr[0])
for i in range(1, n):
for j in range(i):
if arr[i] < arr[j] and (len(l[i]) < len(l[j]) + 1):
l[i] = l[j].copy()
l[i].append(arr[i])
maxx = l[0]
for x in l:
if len(x) > len(maxx):
maxx = x
prints(maxx)
def constructPrintLIS(arr, n):
l = [[] for i in range(n)]
l[0].append(arr[0])
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j] and (len(l[i]) < len (l[j]) + 1):
l[i] = l[j].copy()
l[i].append(arr[i])
maxx = l[0]
for x in l:
if len(x) > len(maxx):
maxx = x
prints(maxx)
if __name__ == "__main__":
arr = list(map(int, input("Enter your input array space separated: ").split()))
n = len(arr)
print("The Longest increasing Subsequence: ")
constructPrintLIS(arr, n)
print("The Longest decreasing Subsequence: ")
constructPrintLDS(arr, n)
Step by step
Solved in 2 steps
