Untitled

import java.util.HashMap;
import java.util.Map;

public class MinSumBinaryTree {
    private Map<String, Integer> memo = new HashMap<>();

    public int mctFromLeafValues(int[] arr) {
        return helper(arr, 0, arr.length - 1);
    }

    private int helper(int[] arr, int left, int right) {
        if (left >= right) return 0; // Base case: single leaf, no non-leaf nodes.

        String key = left + "," + right;
        if (memo.containsKey(key)) return memo.get(key);

        int minSum = Integer.MAX_VALUE;
        for (int k = left; k < right; k++) {
            int leftMax = getMax(arr, left, k);
            int rightMax = getMax(arr, k + 1, right);
            int cost = leftMax * rightMax + helper(arr, left, k) + helper(arr, k + 1, right);
            minSum = Math.min(minSum, cost);
        }

        memo.put(key, minSum);
        return minSum;
    }

    private int getMax(int[] arr, int left, int right) {
        int maxVal = 0;
        for (int i = left; i <= right; i++) {
            maxVal = Math.max(maxVal, arr[i]);
        }
        return maxVal;
    }

    public static void main(String[] args) {
        MinSumBinaryTree solution = new MinSumBinaryTree();
        System.out.println(solution.mctFromLeafValues(new int[]{6, 2, 4})); // Output: 32
        System.out.println(solution.mctFromLeafValues(new int[]{4, 11}));   // Output: 44
    }
}