Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:维护一个不减的栈……

Posted by shh at 2011-05-25 22:00:25 on Problem 2559
In Reply To:维护一个不减的栈…… Posted by:lqp18_31 at 2009-08-04 00:10:11
```zan~

#include <stack>
#include <algorithm>
#include <stdio.h>
using namespace std;

int N;
long long data[100002];

class H{
public:
long long height;
int level;
H(long long h = 0, int l = 0):height(h),level(l){
}
};

stack<H> s;
long long maxSum;

void getMax()
{
while(!s.empty())
{
s.pop();
}

maxSum = -100;

s.push(H(data[1], 1));
for(int i = 2; i <= N+1; i++)
{
long long h = data[i];
if (h >= s.top().height)
{
s.push(H(h, 1));
}
else
{
int l = 0;
while(!s.empty() && h < s.top().height)
{
l += s.top().level;
maxSum = max(maxSum, l * s.top().height);
s.pop();
}
s.push(H(h, l+1));
}
}

printf("%lld\n", maxSum);
}

int main()
{
while(true)
{
scanf("%d ", &N);

if (N == 0)
{
break;
}

for(int i = 1; i <= N; i++)
{
scanf("%lld", &data[i]);
}
data[N+1] = -1;
getMax();
}
}```

Followed by: