• Time:O(n^3)
• Space:O(n^2)

## C++

``````class Solution {
public:
int mctFromLeafValues(vector<int>& arr) {
const int n = arr.size();
// dp[i][j] := min cost of arr[i..j]
vector<vector<int>> dp(n, vector<int>(n));
// maxVal[i][j] := max value of arr[i..j]
vector<vector<int>> maxVal(n, vector<int>(n));

for (int i = 0; i < n; ++i)
maxVal[i][i] = arr[i];

for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
const int j = i + d;
maxVal[i][j] = max(maxVal[i][j - 1], maxVal[i + 1][j]);
}

for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
const int j = i + d;
dp[i][j] = INT_MAX;
for (int k = i; k < j; ++k)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] +
maxVal[i][k] * maxVal[k + 1][j]);
}

return dp[0].back();
}
};
``````

## JAVA

``````class Solution {
public int mctFromLeafValues(int[] arr) {
final int n = arr.length;
// dp[i][j] := min cost of arr[i..j]
int[][] dp = new int[n][n];
// maxVal[i][j] := max value of arr[i..j]
int[][] maxVal = new int[n][n];

for (int i = 0; i < n; ++i)
maxVal[i][i] = arr[i];

for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
final int j = i + d;
maxVal[i][j] = Math.max(maxVal[i][j - 1], maxVal[i + 1][j]);
}

for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
final int j = i + d;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; ++k)
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + maxVal[i][k] * maxVal[k + 1][j]);
}

return dp[0][n - 1];
}
}
``````

## Python

``````class Solution:
def mctFromLeafValues(self, arr: List[int]) -> int:
n = len(arr)
# dp[i][j] := min cost of arr[i..j]
dp = [[0] * n for _ in range(n)]
# maxVal[i][j] := max value of arr[i..j]
maxVal = [[0] * n for _ in range(n)]

for i in range(n):
maxVal[i][i] = arr[i]

for d in range(1, n):
for i in range(n - d):
j = i + d
maxVal[i][j] = max(maxVal[i][j - 1], maxVal[i + 1][j])

for d in range(1, n):
for i in range(n - d):
j = i + d
dp[i][j] = math.inf
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] +
maxVal[i][k] * maxVal[k + 1][j])

return dp[0][-1]
``````

• Time:O(n^2)
• Space:O(n)

## C++

``````class Solution {
public:
int mctFromLeafValues(vector<int>& arr) {
int ans = 0;
vector<int> stack{INT_MAX};

for (const int a : arr) {
while (stack.back() <= a) {
const int mid = stack.back();
stack.pop_back();
// multiply mid with next greater element in the array,
// on the left (stack[-1]) or on the right (current number a)
ans += min(stack.back(), a) * mid;
}
stack.push_back(a);
}

for (int i = 2; i < stack.size(); ++i)
ans += stack[i] * stack[i - 1];

return ans;
}
};
``````

## JAVA

``````class Solution {
public int mctFromLeafValues(int[] arr) {
int ans = 0;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(Integer.MAX_VALUE);

for (final int a : arr) {
while (stack.peek() <= a) {
final int mid = stack.pop();
// multiply mid with next greater element in the array,
// on the left (stack[-1]) or on the right (current number a)
ans += Math.min(stack.peek(), a) * mid;
}
stack.push(a);
}

while (stack.size() > 2)
ans += stack.pop() * stack.peek();

return ans;
}
}
``````

## Python

``````class Solution:
def mctFromLeafValues(self, arr: List[int]) -> int:
ans = 0
stack = [math.inf]

for a in arr:
while stack and stack[-1] <= a:
mid = stack.pop()
# multiply mid with next greater element in the array,
# on the left (stack[-1]) or on the right (current number a)
ans += min(stack[-1], a) * mid
stack.append(a)

return ans + sum(a * b for a, b in zip(stack[1:], stack[2:]))
``````

• Time:O(n)
• Space:O(n)

## C++

``````class Solution:
def mctFromLeafValues(self, arr: List[int]) -> int:
ans = 0

while len(arr) > 1:
i = arr.index(min(arr))
ans += min(arr[i - 1:i] + arr[i + 1:i + 2]) * arr.pop(i)

return ans
``````