Untitled

import java.util.Arrays;

public class MaxStackedCuboids {
    public int maxHeight(int[][] cuboids) {
        int n = cuboids.length;

        // Step 1: Sort dimensions of each cuboid to allow rotation
        for (int[] cuboid : cuboids) {
            Arrays.sort(cuboid);
        }

        // Step 2: Sort cuboids by dimensions: first by width, then length, then height
        Arrays.sort(cuboids, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0]; // Sort by width
            if (a[1] != b[1]) return a[1] - b[1]; // Sort by length
            return a[2] - b[2]; // Sort by height
        });

        // Step 3: Initialize DP array
        int[] dp = new int[n];
        int maxHeight = 0;

        // Base case: The height of each cuboid when used alone
        for (int i = 0; i < n; i++) {
            dp[i] = cuboids[i][2];
        }

        // Step 4: Compute DP
        for (int i = 1; i < n; i++) { // Start with i = 1
            for (int j = 0; j < i; j++) {
                if (cuboids[j][1] <= cuboids[i][1] && cuboids[j][2] <= cuboids[i][2]) {
                    dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
                }
            }
            maxHeight = Math.max(maxHeight, dp[i]); // Update global max height
        }

        return maxHeight;
    }

    public static void main(String[] args) {
        MaxStackedCuboids solution = new MaxStackedCuboids();
        int[][] cuboids1 = {{50, 45, 20}, {95, 37, 53}, {45, 23, 12}};
        int[][] cuboids2 = {{38, 25, 45}, {76, 35, 3}};
        int[][] cuboids3 = {{7, 11, 17}, {7, 17, 11}, {11, 7, 17}, {11, 17, 7}, {17, 7, 11}, {17, 11, 7}};

        System.out.println(solution.maxHeight(cuboids1)); // Output: 190
        System.out.println(solution.maxHeight(cuboids2)); // Output: 76
        System.out.println(solution.maxHeight(cuboids3)); // Output: 102
    }
}