• 높이와 count를 담는 stack 사용
  • stack의 top의 높이 값과 현재 index의 높이 값을 비교
  • stack의 top의 높이 값보다 현재 index의 높이 값이 더 큰 상태일 때까지 pop을 진행
    • 이때, 현재 index에서 pop한 count를 계속 합(sum)하여 값을 축적해놓는다.
    • 지금까지 pop한 count의 sum 값과 pop한 높이 값의 곱이 최댓값인지 확인
  • stack이 비어 있거나, 현재 index의 높이가 더 높아지게 되면 while문을 종료하고 해당 높이와 cntSum에 현재 index에 해당하는 직사각형(1개)을 더한 값을 push
  • stack은 최하위부터 높이의 오름차순으로 정렬이 되는 형태를 유지하게 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65



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

using namespace std;

#define MAX_N 100010
#define ll long long

int N;
ll heights[MAX_N];
ll res;
stack<pair<ll, ll> > st; // <height, count>

void solution() {
	for (int i = 0; i < N; i++) {
		ll curHeight = heights[i];
		ll cntSum = 0; // 이번 index에서 pop한 cnt의 총합

		while (!st.empty()) {
			ll topHeight = st.top().first;
			ll topCnt = st.top().second;

			// top의 높이 값이 같거나 더 높으면 pop하고 pop한 cnt를 cntSum에 더한다
			if (topHeight >= curHeight) { 
				st.pop();
				cntSum += topCnt;
				
				// 이번 index에서 pop한 cnt의 총합과 pop한 높이값의 곱이 최댓값인지 확인
				res = max(res, topHeight * cntSum); 
			} 
			else 
				break;
		}
		
		// stack에는 최하위부터 높이의 오름차순으로 정렬이 되는 형태 
		st.push(make_pair(curHeight, cntSum+1));
	}
	
	ll cntSum = 0;
	while (!st.empty()) {
		ll num = st.top().first;
		ll cnt = st.top().second;
		cntSum += cnt;
		res = max(res, num * cntSum);
		st.pop();
	} 
}

int main() {
	while (true) {
		while (!st.empty()) st.pop();
		res = 0;

		scanf("%d", &N);
		if (N <= 0) break;

		for (int i = 0; i < N; i++)
			scanf("%lld", &heights[i]);

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