Увеличить прямоугольную область под гистограммой

У меня есть гистограмма с целыми высотами и постоянной шириной 1. Я хочу максимизировать прямоугольную область под гистограммой. например:

 _
| |
| |_ 
|   |
|   |_
|     |

Ответом для этого будет 6, 3 * 2, используя col1 и col2.

O (n ^ 2) грубая сила мне понятна, я бы хотел алгоритм O (n log n). Я пытаюсь мыслить динамическое программирование в соответствии с алгоритмом максимального увеличения подпоследовательности O (n log n), но не собираюсь двигаться дальше. Следует ли мне использовать алгоритм «разделяй и властвуй»?

PS: Людей с достаточной репутацией просят удалить тег «разделяй и властвуй», если такого решения нет.

После комментариев mho: я имею в виду площадь самого большого прямоугольника, который подходит полностью. (Спасибо j_random_hacker за разъяснения :))