def find_lis_greedy(seq)
	n = seq.length
	terminals = [0] * (n + 1)
	backptrs = [-1] + [0] * (n - 1)
	
	lis = []
	n_lis = 1
	
	1.upto(n - 1) do |i|
		low = 1
		high = n_lis
		
		while low <= high
			mid = (low + high) / 2
			if seq[i] <= seq[terminals[mid]] 
				high = mid - 1
			else
				low = mid + 1
			end
		end

		terminals[low] = i
		if low <= 1 
			backptrs[i] = -1
		else
			backptrs[i] = terminals[low - 1]
		end
		
		n_lis += 1 if low > n_lis
	end
	
	lis[n_lis - 1] = seq[terminals[n_lis]]
	temp = terminals[n_lis]
	
	(n_lis - 2).downto(0) do |i|
		temp = backptrs[temp]
		lis[i] = seq[temp]
	end
	
	return lis
end