O(n)解決：
高いレベル：
基本的な考え方は、隣接する要素と最小の隣接要素eの両方よりも小さい要素を繰り返しマージすることです。マージのコストと結果の両方がであるため、これにより最小のコストが生成されます。つまり、マージによって要素を現在よりも小さくすることはできません。したがって、可能な限り最も安価なマージはであり、そのマージによって他のコストを増やすことはできません。可能なマージ。nsnlnsmax(a[i],a[i+1])ens
これは、配列の要素のスタックを降順で保持することにより、ワンパスアルゴリズムで実行できます。現在の要素を両方の隣接要素（1つはスタックの最上位）と比較し、完了するまで適切なマージを実行します。
擬似コード：
stack = empty
for pos = 0 to length
// stack.top > arr[pos] is implicitly true because of the previous iteration of the loop
if stack.top > arr[pos] > arr[pos+1]
stack.push(arr[pos])
else if stack.top > arr[pos+1] > arr[pos]
merge(arr[pos], arr[pos+1])
else while arr[pos+1] > stack.top > arr[pos]
merge(arr[pos], stack.pop)
Javaコード：
Stack<Integer> stack = new Stack<Integer>();
int cost = 0;
int arr[] = {10,1,2,3,4,5};
for (int pos = 0; pos < arr.length; pos++)
if (pos < arr.length-1 && (stack.empty() || stack.peek() >= arr[pos+1]))
if (arr[pos] > arr[pos+1])
stack.push(arr[pos]);
else
cost += arr[pos+1]; // merge pos and pos+1
else
{
int last = Integer.MAX_VALUE; // required otherwise a merge may be missed
while (!stack.empty() && (pos == arr.length-1 || stack.peek() < arr[pos+1]))
{
last = stack.peek();
cost += stack.pop(); // merge stack.pop() and pos or the last popped item
}
if (last != Integer.MAX_VALUE)
{
int costTemp = Integer.MAX_VALUE;
if (!stack.empty())
costTemp = stack.peek();
if (pos != arr.length-1)
costTemp = Math.min(arr[pos+1], costTemp);
cost += costTemp;
}
}
System.out.println(cost);