LeetCodeWeekly240 C 1856. Maximum Subarray Min-Product ヒストグラム内の最大長方形の変形 - Qiita

題意 配列の連続した部分列の和 $ \times$ その区間の最小値 の最大値を求めよ 例: $[2,3,3,1,2]$の場合、[3,3]は和6 $times$ min3で18が答えとなる こう考えた ヒストグラムの最大長方形問題に帰着できます。次に図を示します。 上の絵が$[2,3,3]$を選択したとき。下の絵が$[3,3]$を選んだ時です。 ある要素$x$があった時、和がとられることを考えると、長さ$1$の長方形が$x$あると考えてよいです。 実装 さて、要素の数が十分に小さければ、図のようなヒストグラムを実際に配列としてつくって計算しても良いですが、大きい数だと配列が作れません。そのため、区間の和を$O(N)$で求められるように累積和を作ります。 ヒストグラムの最大化の面積を求める際、通常は ある部分の高さ $ \times $ 区間のindexの差 を取りますが、今回は、 ある部分