题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<stack>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;
int n;
int h[N];
int l[N], r[N];

void get(int bound[N])
{
    stack<int> st;
    st.push(0);
    for (int i = 1; i <= n; i ++)
    {
        while(st.size() && h[st.top()] >= h[i]) st.pop();
        bound[i] = st.top();
        st.push(i);
    }
}

int main()
{
    while(cin >> n, n)
    {
        for (int i = 1; i <= n; i ++) cin >> h[i];
        h[0] = -1;
        get(l);
        reverse(h + 1, h + n + 1);
        get(r);



        LL res = 0;
        for (int i = 1, j = n; i <= n; i ++, j --)
            res = max(res, h[i] * (n + 1 - r[i] - l[j] - 1ll));

        cout << res << endl;
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla