51Nod 1102 面积最大的矩形

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stack>
 4 
 5 using namespace std;
 6 const int maxn = 50000 + 5;
 7 long long a[maxn];
 8 long long l[maxn], r[maxn];
 9 
10 int main(){
11     ios::sync_with_stdio(false);
12     int n;
13     cin >> n;
14     for (int i = 1; i <= n; i++){
15         cin >> a[i];
16         l[i] = r[i] = i;
17     }
18     for (int i = 1; i <= n; i++){
19         while (a[l[i]-1] >= a[i]){
20             l[i] = l[l[i] - 1];
21         }
22     }
23 
24     for (int i = n; i >= 1; i--){
25         while (a[i] <= a[r[i] + 1]){
26             r[i] = r[r[i] + 1];
27         }
28     }
29 
30     long long sum = -1;
31     for (int i = 1; i <= n; i++){
32         if (sum < a[i] * (r[i] - l[i] + 1))
33             sum = a[i] * (r[i] - l[i] + 1);
34     }
35     cout << sum << endl;
36     system("pause");
37     return 0;
38 }