最適二分探索木 と同じ問題であることがわかります。

上記リンク先にある解説スライドにあるように、Hu–Tucker algorithm などを用いて \(O(n\log(n))\) 時間で求めることができます。

参考リンク：

• https://math.mit.edu/~shor/PAM/hu-tucker_algorithm.html
  • (archive)
• https://scholarworks.rit.edu/cgi/viewcontent.cgi?article=7489&context=theses

実装のためには、meldable heap と呼ばれるデータ構造が必要になります。通常のヒープの操作に加えて、meld（二つのヒープを融合する操作）を高速に行うデータ構造の総称です。meldable heap には、binomial heap（二項ヒープ。有名な二分ヒープ (binary heap) とは別物）、Fibonacci heap、leftist heap、skew heap などがあります。

todo: Hu–Tucker algorithm の解説を書く。

• Hu–Tucker ベースの愚直な実装：提出 #33573629, \(O(n^3)\) time
• Hu–Tucker algorithm：提出 #34093459, \(O(n \log(n))\) time

なお、Garsia–Wachs algorithm というアルゴリズムも知られているようです。