Largest Rectangle

largestRectangle(height) は、histogram に含まれる最大長方形の面積を求めます。

import

import atcoder/extra/dp/largest_rectangle

使用例

import atcoder/extra/dp/largest_rectangle

let h = @[2, 1, 5, 6, 2, 3]

doAssert largestRectangle(h) == 10

計算量

height.len = n とすると、

• O(n)

です。