Максимизируйте прямоугольную область под гистограммой

Question

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

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

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

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

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

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

Answer 1

Вы можете использовать метод O (n), который использует стек для вычисления максимальной площади под гистограммой.

long long histogramArea(vector<int> &histo){
   stack<int> s;
   long long maxArea=0;
   long long area= 0;
   int i =0;
   for (i = 0; i < histo.size();) {
    if(s.empty() || histo[s.top()] <= histo[i]){
        s.push(i++);
    }
    else{
        int top = s.top(); s.pop();
        area= histo[top]* (s.empty()?i:i-s.top()-1);
        if(area >maxArea)
            maxArea= area;
    }
  }
  while(!s.empty()){
    int top = s.top();s.pop();
    area= histo[top]* (s.empty()?i:i-s.top()-1);
    if(area >maxArea)
        maxArea= area;
 }
 return maxArea;
}

Для объяснения вы можете прочитать здесь http://www.geeksforgeeks.org/largest-rectangle-under-histogram/