package leetcode;

/**
 * https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/
 */
public class Problem1130 {
    public int mctFromLeafValues(int[] arr) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem1130 prob = new Problem1130();
        System.out.println(prob.mctFromLeafValues(new int[]{6, 2, 4})); // 32
        System.out.println(prob.mctFromLeafValues(new int[]{6, 2, 4, 5})); // 58
        System.out.println(prob.mctFromLeafValues(new int[]{6, 2})); // 12
        System.out.println(prob.mctFromLeafValues(new int[]{6, 2, 4, 1, 7})); // 78
    }
}

@@ -174,15 +174,175 @@
     
-// TODO
+return mctFromLeafValues(arr, 0, arr.length - 1).sum;%0A    %7D%0A%0A    private static MaxSum mctFromLeafValues(int%5B%5D array, int start, int end) %7B%0A        if (start == end) %7B
 %0A   
@@ -350,17 +350,687 @@
     
+    
 return 
-0;
+new MaxSum(array%5Bstart%5D, 0);%0A        %7D%0A        int max = 0;%0A        int sum = Integer.MAX_VALUE;%0A        for (int i = start; i %3C end; i++) %7B%0A            MaxSum left = mctFromLeafValues(array, start, i);%0A            MaxSum right = mctFromLeafValues(array, i + 1, end);%0A            max = Math.max(max, Math.max(left.max, right.max));%0A            sum = Math.min(sum, left.sum + right.sum + left.max * right.max);%0A        %7D%0A        return new MaxSum(max, sum);%0A    %7D%0A%0A    private static class MaxSum %7B%0A        private final int max;%0A        private final int sum;%0A%0A        public MaxSum(int max, int sum) %7B%0A            this.max = max;%0A            this.sum = sum;%0A        %7D
 %0A   

Update problem 1130