<p>Given <code>n</code> <code>cuboids</code> where the dimensions of the <code>i<sup>th</sup></code> cuboid is <code>cuboids[i] = [width<sub>i</sub>, length<sub>i</sub>, height<sub>i</sub>]</code> (<strong>0-indexed</strong>). Choose a <strong>subset</strong> of <code>cuboids</code> and place them on each other.</p>

<p>You can place cuboid <code>i</code> on cuboid <code>j</code> if <code>width<sub>i</sub> &lt;= width<sub>j</sub></code> and <code>length<sub>i</sub> &lt;= length<sub>j</sub></code> and <code>height<sub>i</sub> &lt;= height<sub>j</sub></code>. You can rearrange any cuboid&#39;s dimensions by rotating it to put it on another cuboid.</p>

<p>Return <em>the <strong>maximum height</strong> of the stacked</em> <code>cuboids</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/10/21/image.jpg" style="width: 420px; height: 299px;" /></strong></p>

<pre>
<strong>Input:</strong> cuboids = [[50,45,20],[95,37,53],[45,23,12]]
<strong>Output:</strong> 190
<strong>Explanation:</strong>
Cuboid 1 is placed on the bottom with the 53x37 side facing down with height 95.
Cuboid 0 is placed next with the 45x20 side facing down with height 50.
Cuboid 2 is placed next with the 23x12 side facing down with height 45.
The total height is 95 + 50 + 45 = 190.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cuboids = [[38,25,45],[76,35,3]]
<strong>Output:</strong> 76
<strong>Explanation:</strong>
You can&#39;t place any of the cuboids on the other.
We choose cuboid 1 and rotate it so that the 35x3 side is facing down and its height is 76.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
<strong>Output:</strong> 102
<strong>Explanation:</strong>
After rearranging the cuboids, you can see that all cuboids have the same dimension.
You can place the 11x7 side down on all cuboids so their heights are 17.
The maximum height of stacked cuboids is 6 * 17 = 102.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == cuboids.length</code></li>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= width<sub>i</sub>, length<sub>i</sub>, height<sub>i</sub> &lt;= 100</code></li>
</ul>

from typing import List

def is_prev_smaller(x, y):
    """Check if cuboid x can be placed on top of cuboid y."""
    return x[0] <= y[0] and x[1] <= y[1] and x[2] <= y[2]

def f1(cuboids, idx, prev_idx):
    """Calculate the maximum height of stacking cuboids starting from index `idx`."""
    if idx == len(cuboids):
        return 0
    
    # Option to exclude the current cuboid
    exclude = f1(cuboids, idx + 1, prev_idx)
    
    # Option to include the current cuboid
    if prev_idx == -1 or is_prev_smaller(cuboids[idx], cuboids[prev_idx]):
        include = cuboids[idx][2] + f1(cuboids, idx + 1, idx)
    else:
        include = 0
    
    return max(include, exclude)

def f3(arr, n):

    DP = [[0 for _ in range(n+1)] for _ in range(n+1)]
        
    for idx in range(n-1, -1, -1):
        for prev_idx in range(idx-1, -2, -1):
            ans = 0
            if prev_idx == -1 or arr[prev_idx] < arr[idx]:
                ans = max(ans, 1 + DP[idx+1][idx+1])
            ans = max(ans, DP[idx+1][prev_idx+1])
        
            DP[idx][prev_idx+1] = ans
            
    return DP[0][0]

def f3(arr, n):

    DP = [[0 for _ in range(n+1)] for _ in range(n+1)]
        
    for idx in range(n-1, -1, -1):
        for prev_idx in range(idx-1, -2, -1):
            ans = 0
            if prev_idx == -1 or is_prev_smaller(arr[prev_idx], arr[idx]):
                ans = max(ans, arr[idx][2] + DP[idx+1][idx+1])
            ans = max(ans, DP[idx+1][prev_idx+1])
        
            DP[idx][prev_idx+1] = ans
            
    return DP[0][0]

def f4(arr, n):
    """sp op"""

    # DP = [[0 for _ in range(n+1)] for _ in range(n+1)]
    cur_row = [0 for _ in range(n+1)]
    nex_row = [0 for _ in range(n+1)]
        
    for idx in range(n-1, -1, -1):
        for prev_idx in range(idx-1, -2, -1):
            ans = 0
            if prev_idx == -1 or is_prev_smaller(arr[prev_idx], arr[idx]):
                ans = max(ans, arr[idx][2] + nex_row[idx+1])
            ans = max(ans, nex_row[prev_idx+1])
        
            cur_row[prev_idx+1] = ans
        cur_row, nex_row = nex_row, cur_row
            
    return nex_row[0]

def dp_approach(cuboids, n):
    for cub in cuboids:
        cub.sort()
    cuboids.sort(reverse=True, key=lambda x: (x[0], x[1], x[2]))

    dp = [cu[2] for cu in cuboids]     
                                    
    ans = max(dp)
    for i in range(1, n):                                              
        for j in range(i):                                            
            if is_prev_smaller(cuboids[j], cuboids[i]):                             
                dp[i] = max(dp[i], dp[j] + cuboids[i][2])              
        ans = max(ans, dp[i])   
                                                
    return ans

def binary_search_approach(cuboids, n):
    import bisect

    for cub in cuboids:
        cub.sort()
    cuboids.sort(reverse=True, key=lambda x: (x[0], x[1], x[2]))

    dp = []

    print(cuboids)
    for cuboid in cuboids:
        width, length, height = cuboid
        # Perform binary search on dp to find the index to update
        pos = bisect.bisect_left(dp, height)
        print(dp, cuboid, pos)
        if pos == len(dp):
            dp.append(height)
        else:
            dp[pos] = max(dp[pos], height)
        print(dp)
    
    # The maximum height is the sum of heights in dp
    return sum(dp)


class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        n = len(cuboids)

        # return dp_approach(cuboids, n)

        # return binary_search_approach(cuboids, n)

        for cub in cuboids:
            cub.sort()
        cuboids.sort(key=lambda x: (x[0], x[1], x[2]))

        # return f1(cuboids, 0, -1)

        return f3(cuboids, len(cuboids))

        # return f4(cuboids, len(cuboids))
97