Вопрос дает последовательность блоков с одинаковой шириной 1 и разной высотой. Вам нужно найти максимально большие прямоугольники, которые можно составить. Например, самый большой возможный прямоугольник, который может быть сформирован в приведенном ниже примере, — это заштрихованная область:

Один наивный, но интуитивно понятный алгоритм состоит в том, чтобы перебирать каждый блок, проверяя его слева и справа, пока не будет найден более короткий блок с каждой стороны (т. е. найти границы). Таким образом, вы можете найти самый большой прямоугольник с высотой, равной высоте текущего блока. Этот метод грубой силы занимает O(n²) времени.

Лучше использовать увеличивающийся стек. Каждый раз, когда мы вталкиваем новый блок, если вершина стека выше, чем новый блок, это означает, что прямоугольник с верхним блоком достиг своей правой границы (нашел первый более короткий блок справа). Мы можем получить площадь прямоугольника, начиная с верхнего блока, умножив его высоту на расстояние между его левой и правой границей. Но как нам получить левую границу? Когда мы вставляем новый блок, если верхний блок выше, это означает, что прямоугольник, начинающийся с этого нового блока, может продолжаться влево до верхнего блока (поскольку верхний блок выше), поэтому мы обновляем левую границу этого нового блока. блокировать. Если верхний блок уже короче нового блока, то его левая граница — это он сам. (Если queal high, может быть обработан любым способом.) После этого мы можем вытолкнуть верхний блок. Мы повторяем это до тех пор, пока стек не станет пустым или верхний блок не станет короче нового блока. Затем мы можем просто вставить новый блок.

Мы можем использовать структуру блока для хранения его левой границы и высоты.

После обработки всех блоков, если в стеке остались блоки, это означает, что у этих блоков нет правильных границ (если они есть, они уже будут вытолкнуты). Следовательно, прямоугольники, начинающиеся с них, могут простираться до самого правого блока.

Коды:

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long ll;
const int MAX = 100005;
typedef pair<int, ll> rect;
//build an increasing stack
void max_rect(int N){2
    ll h, temp_area, max_area=0;
    rect t;
    stack<rect> stk;
    for(int i=0; i<N; i++){
        scanf("%lld", &h);
        t = rect(i, h);
        //met right limit of rect
        while(!stk.empty() && stk.top().second >= h){
            t = stk.top();
            stk.pop();
            
            temp_area = (i - t.first)*t.second;
            max_area = max(temp_area, max_area);
        }
        //t.first: left limit to extend
        stk.push(rect(t.first, h));
    }
    while(!stk.empty()){
        t = stk.top();
        stk.pop();
        temp_area = (N - t.first)*t.second;
        max_area = max(temp_area, max_area);
    }
    printf("%lld\n", max_area);
}
int main(){
    int N;
    while(scanf("%d", &N) && N){
        max_rect(N);
    }
}