<p>Given an array <code>arr</code> of positive integers, consider all binary trees such that:</p>

<ul>
	<li>Each node has either <code>0</code> or <code>2</code> children;</li>
	<li>The values of <code>arr</code> correspond to the values of each <strong>leaf</strong> in an in-order traversal of the tree.</li>
	<li>The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree, respectively.</li>
</ul>

<p>Among all possible binary trees considered, return <em>the smallest possible sum of the values of each non-leaf node</em>. It is guaranteed this sum fits into a <strong>32-bit</strong> integer.</p>

<p>A node is a <strong>leaf</strong> if and only if it has zero children.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/10/tree1.jpg" style="width: 500px; height: 169px;" />
<pre>
<strong>Input:</strong> arr = [6,2,4]
<strong>Output:</strong> 32
<strong>Explanation:</strong> There are two possible trees shown.
The first has a non-leaf node sum 36, and the second has non-leaf node sum 32.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/10/tree2.jpg" style="width: 224px; height: 145px;" />
<pre>
<strong>Input:</strong> arr = [4,11]
<strong>Output:</strong> 44
</pre>

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

<ul>
	<li><code>2 &lt;= arr.length &lt;= 40</code></li>
	<li><code>1 &lt;= arr[i] &lt;= 15</code></li>
	<li>It is guaranteed that the answer fits into a <strong>32-bit</strong> signed integer (i.e., it is less than 2<sup>31</sup>).</li>
</ul>

class Solution {
public:
/*
    int fun(vector<int>& arr, int left, int right, vector<vector<int>>& dp)
    {
        if(left >= right)
            return 0;
        if(dp[left][right] != -1)
            return dp[left][right];

        int ans = INT_MAX;
        for(int k = left; k < right; k++)
        {
            int leftMax = INT_MIN;
            int rightMax = INT_MIN;
            for(int i = left; i <= k; i++)
                if(arr[i] > leftMax)
                    leftMax = arr[i];
            for(int i = k + 1; i <= right; i++)
                if(arr[i] > rightMax)
                    rightMax = arr[i];       

            ans = min(ans, leftMax * rightMax + fun(arr, left, k, dp) + fun(arr, k + 1, right, dp)); 
        }
        
        return dp[left][right] = ans;
    }*/
    int mctFromLeafValues(vector<int>& arr)
    {
        int n = arr.size();
        int ans = 0;
        stack<int> st;
        st.push(INT_MAX);

        for(int num : arr)
        {
            while(!st.empty() && st.top() < num) // greater number found remove previous min
            {
                int small = st.top();
                st.pop();
                if(!st.empty())
                    ans += small * min(num, st.top());
            }
            st.push(num);
        }

        while(st.size() > 2)
        {
            int small = st.top();
            st.pop();
            ans += small * st.top();
        }

        return ans;
    }
};

/*

Greedy approach -

Try to keep larger numbers close to root, so they multiply less times
Try to remove minimum elements first and add the product to ans

                48       
            8       24
                12      6      
            4        6      
                2       3

8 4 2 3 6

8 4 3 6 ; 2*3
8 4 6 ; 3*4
8 6 ; 4*6
8 ; 8*6

Decreasing stack ?

8
8 4
8 4 2
8 4 3 ; 2*3
8 4 ; 3*4
8 6 ; 4*6
8 ; 8*6

DP try to split at each index and then at k

dp[i][j] = max(i to k) * max(k + 1 to j) + dp[i][k] + dp[k + 1][j]

Array has only leaf nodes - 
n leaves => nodes ?

3 leaves => 2 non leaf
4 leaves => 3 non leaf

n - 1 non leaf

4 11 => [4][11] => 44

6 2 4 => [6 2][4] ; [6][2 4] => 12 + 24 ; 8 + 24

1 2 3 4 => [1][2 3 4] ; [1 2][3 4] ; [1 2 3][4]
           [1][2][3 4]

*/
10400