Given an integer n and array of integers, returns the Longest Increasing subsequence which is lexicographically smallest corresponding to the indices of the elements.
LIS  of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}. 
 
Note - A subsequence S1 is lexicographically smaller than a subsequence S2 if in the first position where a and b differ, subsequence a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example , {1, 2, 3, 6, 7} is lexographically smaller than {1, 2, 3, 8, 10} and {1, 2, 3} is lexographically smaller than {1, 2, 3, 1}.
 
Example 1:
Input:
n = 16
arr = [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
Output:
0 4 6 9 13 15 
Explanation:
longest Increasing subsequence is 0 4 6 9 13 15  and the length of the longest increasing subsequence is 6.
Example 2:
Input:
n = 1
arr = [1]
Output:
1
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestIncreasingSubsequence() which takes integer n and array arr and returns the longest increasing subsequence.
Expected Time Complexity: O(n^{2})
Expected Space Complexity: O(n)
Constraint:
1 <= n < = 1000
1 <= arr[i] <= 50000

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def longestIncreasingSubsequence(self, N, arr):

        # Code here

Solutions:
class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		(res, dp, path) = ([], [1] * N, [i for i in range(N)])
		lisInd = lis = 0
		for i in range(N):
			for prev in range(i):
				if arr[prev] < arr[i] and dp[prev] + 1 > dp[i]:
					dp[i] = dp[prev] + 1
					path[i] = prev
					if dp[i] > lis:
						lis = dp[i]
						lisInd = i
		while path[lisInd] != lisInd:
			res.append(arr[lisInd])
			lisInd = path[lisInd]
		res.append(arr[lisInd])
		return res[::-1]


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		dp = [1] * N
		p = [-1] * N
		(max, pos) = (0, -1)
		for i in range(N):
			for j in range(i):
				if arr[i] > arr[j] and dp[i] < dp[j] + 1:
					dp[i] = dp[j] + 1
					p[i] = j
			if max < dp[i]:
				max = dp[i]
				pos = i
		ans = [0] * max
		for i in range(max - 1, -1, -1):
			ans[i] = arr[pos]
			pos = p[pos]
		return ans


class Solution:

	def longestIncreasingSubsequence(self, n, a):
		dp = [1] * n
		hash = [0] * n
		maxi = 1
		lastindex = 0
		for ind in range(n):
			hash[ind] = ind
			for prev in range(ind):
				if a[prev] < a[ind] and 1 + dp[prev] > dp[ind]:
					dp[ind] = 1 + dp[prev]
					hash[ind] = prev
			if dp[ind] > maxi:
				maxi = dp[ind]
				lastindex = ind
		temp = []
		temp.append(a[lastindex])
		while hash[lastindex] != lastindex:
			lastindex = hash[lastindex]
			temp.append(a[lastindex])
		temp.reverse()
		return temp


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		table = [1 for i in range(N)]
		hash = [0 for i in range(N)]
		maxiValue = 1
		lastIndex = 0
		for index in range(N):
			hash[index] = index
			for prev in range(index):
				if arr[prev] < arr[index] and table[index] < table[prev] + 1:
					table[index] = table[prev] + 1
					hash[index] = prev
			if table[index] > maxiValue:
				maxiValue = table[index]
				lastIndex = index
		ans = []
		ans.append(arr[lastIndex])
		while hash[lastIndex] != lastIndex:
			lastIndex = hash[lastIndex]
			ans.append(arr[lastIndex])
		ans = ans[::-1]
		return ans


class Solution:

	def longestIncreasingSubsequence(self, n, a):
		dp = []
		for i in range(n):
			dp.append(0)
		dp[n - 1] = 1
		for i in range(1, n):
			maxi = -2
			flag = 0
			for j in range(n - i, n):
				if a[j] > a[n - i - 1] and dp[j] > maxi:
					maxi = dp[j]
					flag = 1
			dp[n - i - 1] = 1 + maxi
			if flag == 0:
				dp[n - i - 1] = 1
		ans = []
		l = 0
		fin = max(dp)
		for i in range(fin, 0, -1):
			while i != dp[l]:
				l += 1
			ans.append(a[l])
		return ans


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		maxi = 0
		dp = [1] * N
		hash = [1] * N
		last_idx = -1
		for i in range(N):
			hash[i] = i
			for j in range(i):
				if arr[i] > arr[j] and 1 + dp[j] > dp[i]:
					dp[i] = 1 + dp[j]
					hash[i] = j
			if maxi < dp[i]:
				maxi = dp[i]
				last_idx = i
		ans = []
		ans.append(arr[last_idx])
		while hash[last_idx] != last_idx:
			ans.append(arr[hash[last_idx]])
			last_idx = hash[last_idx]
		ans = list(reversed(ans))
		return ans


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		dp = [1 for i in range(N)]
		hash = [1 for i in range(N)]
		maxi = 1
		lastidx = 0
		for i in range(N):
			hash[i] = i
			for prev in range(i + 1):
				if arr[prev] < arr[i] and 1 + dp[prev] > dp[i]:
					dp[i] = 1 + dp[prev]
					hash[i] = prev
				if dp[i] > maxi:
					maxi = dp[i]
					lastidx = i
		temp = []
		temp.append(arr[lastidx])
		while hash[lastidx] != lastidx:
			lastidx = hash[lastidx]
			temp.append(arr[lastidx])
		temp = temp[::-1]
		return temp


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		n = N
		a = arr
		dp = [1] * n
		ans = [i for i in range(n)]
		maxi = -1
		max_no = -1
		for i in range(n):
			for j in range(i):
				if a[j] < a[i]:
					if dp[i] < 1 + dp[j]:
						dp[i] = 1 + dp[j]
						ans[i] = j
						if dp[i] > max_no:
							maxi = i
							max_no = dp[i]
		r_ans = []
		if maxi == -1:
			return [a[0]]
		while ans[maxi] != maxi:
			r_ans.append(a[maxi])
			maxi = ans[maxi]
		r_ans.append(a[maxi])
		r_ans.reverse()
		return r_ans


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		dp = [1 for i in range(N)]
		res = [i for i in range(N)]
		for i in range(N):
			for j in range(i):
				if arr[i] > arr[j] and 1 + dp[j] > dp[i]:
					dp[i] = 1 + dp[j]
					res[i] = j
		count = -1
		indx = -1
		for k in range(N):
			if dp[k] > count:
				count = dp[k]
				indx = k
		ans = []
		ans.append(arr[indx])
		while res[indx] != indx:
			indx = res[indx]
			ans.append(arr[indx])
		ans.reverse()
		return ans


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		a = arr
		n = N
		dp = {}
		hash = {}
		for i in range(n):
			dp[i] = 1
			hash[i] = -1
		answer = 0
		answerIndex = -1
		for i in range(1, n):
			maxSoFar = dp[i]
			prev = -1
			for j in range(i):
				curr = 1 + dp[j] if a[j] < a[i] else -float('inf')
				if curr > maxSoFar:
					maxSoFar = curr
					prev = j
			dp[i] = maxSoFar
			hash[i] = prev
			if dp[i] > answer:
				answer = max(answer, dp[i])
				answerIndex = i
		lis = []
		while answerIndex != -1:
			lis.insert(0, a[answerIndex])
			answerIndex = hash[answerIndex]
		return lis


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		n = N
		prev = [i for i in range(n)]
		dp = [1] * n
		maxi = 0
		last = 0
		for i in range(n):
			for j in range(i):
				if arr[i] > arr[j]:
					if dp[j] + 1 > dp[i]:
						dp[i] = dp[j] + 1
						prev[i] = j
			if dp[i] > maxi:
				maxi = dp[i]
				last = i
		ans = []
		while prev[last] != last:
			ans.append(arr[last])
			last = prev[last]
		ans.append(arr[last])
		ans.reverse()
		return ans


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		n = N
		dp = [1 for i in range(n)]
		hash = [1 for i in range(n)]
		for i in range(n):
			hash[i] = i
			for prev_ind in range(i):
				if arr[prev_ind] < arr[i] and 1 + dp[prev_ind] > dp[i]:
					dp[i] = 1 + dp[prev_ind]
					hash[i] = prev_ind
		ans = -1
		lastIndex = -1
		for i in range(n):
			if dp[i] > ans:
				ans = dp[i]
				lastIndex = i
		temp = []
		temp.append(arr[lastIndex])
		while hash[lastIndex] != lastIndex:
			lastIndex = hash[lastIndex]
			temp.append(arr[lastIndex])
		return temp[::-1]


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		n = N
		dp = [1 for _ in range(n)]
		has = [i for i in range(n)]
		for ind in range(n):
			for prev in range(ind):
				if arr[prev] < arr[ind] and 1 + dp[prev] > dp[ind]:
					dp[ind] = 1 + dp[prev]
					has[ind] = prev
		ans = -1
		last = -1
		for ind in range(n):
			if dp[ind] > ans:
				ans = dp[ind]
				last = ind
		temp = []
		temp.append(arr[last])
		while has[last] != last:
			last = has[last]
			temp.append(arr[last])
		return temp[::-1]


class Solution:

	def longestIncreasingSubsequence(self, n, a):
		h = [i for i in range(n)]
		dp = [1] * n
		(li, ma) = (0, 1)
		for i in range(n):
			h[i] = i
			for pre in range(0, i):
				if a[pre] < a[i] and 1 + dp[pre] > dp[i]:
					dp[i] = 1 + dp[pre]
					h[i] = pre
			if dp[i] > ma:
				ma = dp[i]
				li = i
		ans = []
		ans.append(a[li])
		while h[li] != li:
			li = h[li]
			ans.append(a[li])
		ans.sort()
		return ans


class Solution:

	def longestIncreasingSubsequence(self, N, nums):
		n = len(nums)
		dp = [[x] for x in nums]
		for i in range(n - 2, -1, -1):
			for j in range(i + 1, n):
				if nums[i] < nums[j]:
					if len(dp[i]) < 1 + len(dp[j]):
						dp[i] = [nums[i]] + dp[j]
		res = []
		for i in range(n):
			if len(res) < len(dp[i]):
				res = dp[i]
		return res


class Solution:

	def longestIncreasingSubsequence(self, N, nums):
		N = len(nums)
		dp = [0] * N
		prev = {}
		besti = -1
		for i in range(N):
			if i == 0:
				dp[i] = 1
				continue
			ans = 1
			for j in range(i):
				prevLIS = dp[j]
				if nums[i] > nums[j] and prevLIS + 1 >= ans:
					if i not in prev or prevLIS + 1 > ans or nums[j] > nums[prev[i]]:
						prev[i] = j
					ans = max(ans, prevLIS + 1)
			dp[i] = ans
			if besti < 0 or dp[besti] < ans:
				besti = i
		i = besti
		ans = [nums[i]]
		while i in prev:
			ans.append(nums[prev[i]])
			i = prev[i]
		ans.reverse()
		return ans


class Solution:

	def longestIncreasingSubsequence(self, n, arr):
		Dp = [1] * n
		indStore = [i for i in range(n)]
		maxxVal = 1
		lastInd = 0
		for i in range(1, n):
			for prev in range(i):
				if arr[prev] < arr[i] and Dp[prev] + 1 >= Dp[i]:
					if Dp[prev] + 1 > Dp[i]:
						Dp[i] = Dp[prev] + 1
						indStore[i] = prev
					elif indStore[i] != i and arr[indStore[i]] < arr[prev]:
						indStore[i] = prev
			if maxxVal <= Dp[i]:
				if maxxVal < Dp[i]:
					maxxVal = Dp[i]
					lastInd = i
				elif arr[lastInd] < arr[i]:
					lastInd = i
		ans = [0] * maxxVal
		ind = maxxVal - 1
		ans[ind] = arr[lastInd]
		while indStore[lastInd] != lastInd:
			ind -= 1
			lastInd = indStore[lastInd]
			ans[ind] = arr[lastInd]
		return ans


class Solution:

	def longestIncreasingSubsequence(self, n, arr):
		dp = [1] * n
		hash = [1] * n
		last_idx = 0
		maxi = 1
		for idx in range(n):
			hash[idx] = idx
			for prev in range(idx):
				if arr[prev] < arr[idx] and 1 + dp[prev] > dp[idx]:
					dp[idx] = 1 + dp[prev]
					hash[idx] = prev
			if dp[idx] > maxi:
				maxi = dp[idx]
				last_idx = idx
		temp = []
		temp.append(arr[last_idx])
		while hash[last_idx] != last_idx:
			last_idx = hash[last_idx]
			temp.append(arr[last_idx])
		temp.reverse()
		return temp


class Solution:

	def longestIncreasingSubsequence(self, n, nums):
		dp = [1 for _ in range(n)]
		back = [0 for _ in range(n)]
		(maxi, last_index) = (0, 0)
		for i in range(1, n):
			back[i] = i
			for prev_index in range(0, i):
				if nums[i] > nums[prev_index] and 1 + dp[prev_index] > dp[i]:
					dp[i] = 1 + dp[prev_index]
					back[i] = prev_index
			if maxi < dp[i]:
				maxi = dp[i]
				last_index = i
		temp = [nums[last_index]]
		while back[last_index] != last_index:
			last_index = back[last_index]
			temp.append(nums[last_index])
		return reversed(temp[:])


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		dp = [1 for i in range(N)]
		ind = [i for i in range(N)]
		for i in range(N):
			for j in range(i):
				if arr[i] > arr[j]:
					if 1 + dp[j] > dp[i]:
						dp[i] = 1 + dp[j]
						ind[i] = j
					if dp[i] == 1 + dp[j]:
						if arr[j] > arr[ind[i]]:
							ind[i] = j
		maxi = 0
		maxii = 0
		for i in range(N):
			if maxi < dp[i]:
				maxi = dp[i]
				maxii = i
		l = []
		l.append(arr[maxii])
		while maxii != ind[maxii]:
			maxii = ind[maxii]
			l.append(arr[maxii])
		return l[::-1]


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		dp = [-1 for i in range(N)]
		dp[0] = [arr[0]]
		ans = 0
		for i in range(1, N):
			dp[i] = [arr[i]]
			for j in range(i - 1, -1, -1):
				if dp[j][-1] < dp[i][-1] and len(dp[j]) + 1 >= len(dp[i]):
					dp[i] = dp[j] + [arr[i]]
			if ans < len(dp[i]):
				ans = len(dp[i])
		sol = None
		for i in dp:
			if len(i) == ans:
				if sol is None or sol > i:
					sol = i
					break
		return sol


class Solution:
	result = []

	def dfs(self, arr, N, i, temp):
		if i >= N:
			if len(self.result) < len(temp):
				self.result = temp[:]
			return
		if len(temp) == 0 or arr[i] > temp[-1]:
			temp.append(arr[i])
			self.dfs(arr, N, i + 1, temp)
			temp.pop()
		self.dfs(arr, N, i + 1, temp)

	def longestIncreasingSubsequence(self, N, arr):
		dp = [1] * N
		hash = [0] * N
		max_len = 0
		last_index = 0
		for i in range(N):
			hash[i] = i
			for prev in range(i + 1):
				if arr[i] > arr[prev] and dp[i] < 1 + dp[prev]:
					dp[i] = 1 + dp[prev]
					hash[i] = prev
			if dp[i] > max_len:
				max_len = dp[i]
				last_index = i
		result = [arr[last_index]]
		while hash[last_index] != last_index:
			last_index = hash[last_index]
			result.append(arr[last_index])
		return result[::-1]


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		maximum = 1
		last = 0
		dp = [1] * N
		parent = [i for i in range(N)]
		for i in range(N):
			for j in range(i):
				if arr[i] > arr[j] and dp[i] < dp[j] + 1:
					dp[i] = dp[j] + 1
					parent[i] = j
			if dp[i] > maximum:
				maximum = dp[i]
				last = i
		ans = []
		ans.append(arr[last])
		while parent[last] != last:
			last = parent[last]
			ans.append(arr[last])
		return ans[::-1]


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		dp = []
		hash = []
		for i in range(N):
			dp.append(1)
			hash.append(i)
		lastIndex = 0
		maxi = 1
		for i in range(N):
			for prev in range(0, i):
				if arr[prev] < arr[i] and 1 + dp[prev] > dp[i]:
					dp[i] = 1 + dp[prev]
					hash[i] = prev
			if dp[i] > maxi:
				maxi = dp[i]
				lastIndex = i
		ans = [arr[lastIndex]]
		while lastIndex != hash[lastIndex]:
			ans.append(arr[hash[lastIndex]])
			lastIndex = hash[lastIndex]
		ans = ans[::-1]
		return ans


class Solution:

	def longestIncreasingSubsequence(self, N, nums):
		n = len(nums)
		dp = [1 for _ in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(i, n):
				if nums[i] < nums[j]:
					dp[i] = max(dp[i], 1 + dp[j])
		length = max(dp)
		res = []
		i = 0
		while length > 0 and i < n:
			if dp[i] == length:
				res.append(nums[i])
				length -= 1
			i += 1
		return res


class Solution:

	def longestIncreasingSubsequence(self, n, nums):
		n = len(nums)
		maxi = 1
		dp = [1] * n
		lastidx = 0
		has = [None] * n
		for idx in range(n):
			has[idx] = idx
			for prev_idx in range(idx):
				if nums[prev_idx] < nums[idx] and 1 + dp[prev_idx] > dp[idx]:
					dp[idx] = 1 + dp[prev_idx]
					has[idx] = prev_idx
			if dp[idx] > maxi:
				maxi = dp[idx]
				lastidx = idx
		temp = []
		temp.append(nums[lastidx])
		while has[lastidx] != lastidx:
			lastidx = has[lastidx]
			temp.append(arr[lastidx])
		temp.reverse()
		return temp


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		dp = [1 for i in range(N)]
		hash = [i for i in range(N)]
		start = 0
		maxi = -1000000000.0
		for i in range(N):
			for j in range(i):
				if arr[j] < arr[i]:
					if dp[i] < dp[j] + 1:
						dp[i] = dp[j] + 1
						hash[i] = j
			if dp[i] > maxi:
				maxi = dp[i]
				start = i
		t = start
		res = [arr[start]]
		while hash[t] != t:
			t = hash[t]
			res.append(arr[t])
		return res[::-1]


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		dp = [1 for i in range(N)]
		has = [1 for i in range(N)]
		maxi = 1
		last = 0
		for i in range(N):
			has[i] = i
			for j in range(i):
				if arr[j] < arr[i] and dp[i] < dp[j] + 1:
					dp[i] = dp[j] + 1
					has[i] = j
			if maxi < dp[i]:
				maxi = dp[i]
				last = i
		temp = []
		temp.append(arr[last])
		while has[last] != last:
			last = has[last]
			temp.append(arr[last])
		temp.reverse()
		return temp


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		dp = [1] * N
		hash = [i for i in range(N)]
		maxi = [0, 0]
		for i in range(N):
			for prev in range(i):
				if arr[i] > arr[prev] and dp[i] < dp[prev] + 1:
					dp[i] = dp[prev] + 1
					if dp[i] > maxi[0]:
						maxi[0] = dp[i]
						maxi[1] = i
					hash[i] = prev
		from collections import deque
		res = deque()
		i = maxi[1]
		res.appendleft(arr[i])
		while hash[i] != i:
			i = hash[i]
			res.appendleft(arr[i])
		return res


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		lis = [1] * N
		prev = [i for i in range(N)]
		if arr[0] == 0:
			prev[0] = 0
		lastidx = 0
		maxans = 0
		for i in range(1, N):
			for j in range(0, i):
				if arr[j] < arr[i] and lis[i] <= lis[j]:
					lis[i] = 1 + lis[j]
					prev[i] = j
			if lis[i] > maxans:
				maxans = lis[i]
				lastidx = i
		ans = []
		ans.append(arr[lastidx])
		idx = lastidx
		while prev[idx] != idx:
			idx = prev[idx]
			ans.append(arr[idx])
		ans.reverse()
		return ans


class Solution:

	def longestIncreasingSubsequence(self, N, nums):
		(n, ans) = (len(nums), -1)
		dp = [1 for _ in range(n)]
		hash_ = [i for i in range(n)]
		last = -1
		temp = []
		for i in range(n):
			for j in range(i):
				if nums[i] > nums[j] and 1 + dp[j] > dp[i]:
					dp[i] = max(dp[i], 1 + dp[j])
					hash_[i] = j
			if dp[i] > ans:
				ans = dp[i]
				last = i
		temp.append(nums[last])
		while hash_[last] != last:
			last = hash_[last]
			temp.append(nums[last])
		temp.reverse()
		return temp


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		ans = 1
		lastIndex = 0
		hashh = [i for i in range(N)]
		dp = [1 for i in range(N)]
		for i in range(N):
			for prev in range(i):
				if arr[prev] < arr[i] and dp[i] < 1 + dp[prev]:
					dp[i] = 1 + dp[prev]
					hashh[i] = prev
			if dp[i] > ans:
				ans = dp[i]
				lastIndex = i
		lis = []
		lis.append(arr[lastIndex])
		while lastIndex != hashh[lastIndex]:
			lastIndex = hashh[lastIndex]
			lis.append(arr[lastIndex])
		lis.reverse()
		return lis


class Solution:

	def longestIncreasingSubsequence(self, n, nums):
		dp = [1] * n
		backtrack = [i for i in range(n)]
		lis = dp[0]
		lastIndex = 0
		for ind in range(1, n):
			for prev in range(ind):
				if nums[prev] < nums[ind] and dp[ind] < dp[prev] + 1:
					dp[ind] = dp[prev] + 1
					backtrack[ind] = prev
			if dp[ind] > lis:
				lis = dp[ind]
				lastIndex = ind
		ans = [0] * lis
		ans[0] = arr[lastIndex]
		ind = 1
		while backtrack[lastIndex] != lastIndex:
			lastIndex = backtrack[lastIndex]
			ans[ind] = arr[lastIndex]
			ind += 1
		return ans[::-1]


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		return self.printLis(arr, N)

	def printLis(self, arr, n):
		dp = [1] * n
		hashm = [i for i in range(n)]
		for ind in range(0, n):
			hashm[ind] = ind
			for prev in range(ind):
				if arr[prev] < arr[ind] and 1 + dp[prev] > dp[ind]:
					dp[ind] = 1 + dp[prev]
					hashm[ind] = prev
		lastind = -1
		lenLCS = -1
		for i in range(n):
			if dp[i] > lenLCS:
				lastind = i
				lenLCS = dp[i]
		ans = []
		ans.append(arr[lastind])
		while hashm[lastind] != lastind:
			lastind = hashm[lastind]
			ans.append(arr[lastind])
		return ans[::-1]


class Solution:

	def longestIncreasingSubsequence(self, n, arr):
		dp = [1] * n
		pos = [1] * n
		for i in range(n):
			pos[i] = i
			for prev_index in range(i):
				if arr[prev_index] < arr[i] and 1 + dp[prev_index] > dp[i]:
					dp[i] = 1 + dp[prev_index]
					pos[i] = prev_index
		ans = lastIndex = -1
		for i in range(n):
			if dp[i] > ans:
				ans = dp[i]
				lastIndex = i
		temp = []
		temp.append(arr[lastIndex])
		while pos[lastIndex] != lastIndex:
			lastIndex = pos[lastIndex]
			temp.append(arr[lastIndex])
		return temp[::-1]


class Solution:

	def longestIncreasingSubsequence(self, N, arr):
		lis = [1 for i in range(N)]
		hashh = [int(i) for i in range(N)]
		for i in range(N):
			for j in range(i):
				if arr[j] < arr[i] and 1 + lis[j] > lis[i]:
					lis[i] = 1 + lis[j]
					hashh[i] = j
		maxLIS = 1
		maxInd = 0
		for i in range(N):
			if lis[i] > maxLIS:
				maxLIS = lis[i]
				maxInd = i
		ans = [arr[maxInd]]
		while hashh[maxInd] != maxInd:
			maxInd = hashh[maxInd]
			ans.append(arr[maxInd])
		return ans[-1::-1]


from bisect import bisect_left

class Solution:

	def longestIncreasingSubsequence(self, N, nums):
		fr = [-1] * N
		dp = [1] * N
		mi = 0
		ml = 1
		for i in range(1, N):
			for j in range(i):
				if nums[i] > nums[j] and dp[i] < 1 + dp[j]:
					dp[i] = 1 + dp[j]
					fr[i] = j
			if dp[i] > ml:
				ml = dp[i]
				mi = i
		res = []
		while mi != -1:
			res.append(nums[mi])
			mi = fr[mi]
		return res[::-1]