Longest Increasing Subsequence

test1.py

def lis(arr,n):
	dp = [1 for x in range(0,n)]
	for i in range(1,n):
		for j in range(0,i):
			if dp[j] >= dp[i] and arr[j] < arr[i]:
				dp[i]+=1
	max_value = max(dp)
	result = []
	for i in range(n-1,-1,-1):
		if dp[i] == max_value:
			result.append(arr[i])
			max_value -= 1
	result.reverse()
	return result		
	
n = int(input())
arr = [int(x) for x in input().split()]
print(lis(arr,n))