题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;
const int N = 100010;
typedef long long LL;
int l[N] , r[N] , tmp[N] , que[N];

int main()
{
    int n;
    LL res = 0;
    while(cin >> n , n)
    {
        for(int i = 1; i <= n; i ++)
        {
            cin >> tmp[i];
            //我们找到所有的以其为上封顶的块来求面积
        }
        tmp[0] = tmp[n + 1] = -1;
        int q = -1;
        que[++q] = 0;        
        for(int i = 1; i <= n ; i ++)
        {   //这里我们要做的是什么呢？
            while( q && tmp[que[q]] >= tmp[i] ) q--;
            l[i] = que[q];  //que[q]存储的是    
            que[++q] = i;
        }
        //l[1] = que[0] = 0;
        /*
        que[1] = 1;
        q = 1;
        while(q == 1 && tmp[que[1]] == 2 )
        */
        q = -1;
        que[++q] = n + 1;
        for(int i = n; i >= 1; i --)
        {
            while( q && tmp[que[q]] >= tmp[i] ) q--;
            r[i] = que[q];
            que[++q] = i;
        }
        /*for(int i = 1; i <= n ; i ++)
        {
            cout << "第" << i << "个数字的左面是" << l[i] << "右面" << r[i] << endl;
        }*/
        res = 0;
        for(int i = 1; i <= n; i ++)
        {
            res = max(res , (LL)tmp[i] * (r[i] - l[i] - 1));
        }
        cout << res << endl;
    }
    return 0;
}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla