human
Give me a code to largest subset of rectangles such that no rectangle fit in any other rectangle and the other steps required given the following:
Largest subset of rectangles such that no rectangle fit in any other rectangle | Recursive function to get the largest subset.
Base case when it exceeds.
If the state has been visited previously.
Initialize.
No elements in subset yet.
First state which includes current index.
Second state which does not include current index.
If the rectangle fits in , then do not include the current index in subset.
First state which includes current index.
Second state which does not include current index.
Function to get the largest subset.
Sort the array.
Get the answer.
Driver code.
( height , width ) pairs"
How can the above be solved in Python?
assistant
#Here is code to largest subset of rectangles such that no rectangle fit in any other rectangle and the other steps required.
 def findLongest ( a , n , present , previous ) :
	if present == n :
		return 0
	elif previous != - 1 :
		if dp [ present ] [ previous ] != - 1 :
			return dp [ present ] [ previous ]
	ans = 0
	if previous == - 1 :
		ans = 1 + findLongest ( a , n , present + 1 , present )
		ans = max ( ans , findLongest ( a , n , present + 1 , previous ) )
	else :
		h1 = a [ previous ] [ 0 ]
		h2 = a [ present ] [ 0 ]
		w1 = a [ previous ] [ 1 ]
		w2 = a [ present ] [ 1 ]
		if h1 <= h2 and w1 <= w2 :
			ans = max ( ans , findLongest ( a , n , present + 1 , previous ) )
		else :
			ans = 1 + findLongest ( a , n , present + 1 , present )
			ans = max ( ans , findLongest ( a , n , present + 1 , previous ) )
	dp [ present ] [ previous ] = ans
	return ans
def getLongest ( a , n ) :
	a . sort ( )
	ans = findLongest ( a , n , 0 , - 1 )
	return ans
if __name__ == " _ _ main _ _ " :
	a = [ [ 1 , 5 ] , [ 2 , 4 ] , [ 1 , 1 ] , [ 3 , 3 ] ]
	N = 10
	dp = [ [ - 1 for i in range ( N ) ] for j in range ( N ) ]
	n = len ( a )
	print ( getLongest ( a , n ) )