单调栈算法。

#include <bits/stdc++.h>


using namespace std;


long long h[100010];


struct rect_t {
    long long height, len;
};


int main(void) {
    int n;
    while ((scanf("%d", &n), n) != 0) {
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &h[i]);
        }
        h[n + 1] = 0;

        stack<rect_t> rects_st;
        long long res = 0;
        for (int i = 1; i <= n + 1; ++i) {
            long long sum_len = 0;
            while (!rects_st.empty() && rects_st.top().height >= h[i]) {
                sum_len += rects_st.top().len;
                res = max(res, sum_len * rects_st.top().height);
                rects_st.pop();
            }

            rect_t tmp;
            tmp.height = h[i];
            tmp.len = sum_len + 1;
            rects_st.push(tmp);
        }

        printf("%lld\n", res);
    }
    return 0;
}