[알고리즘] 백준 6549번: 히스토그램에서 가장 큰 직사각형 (C++)

https://www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

직전의 포스팅과 똑같은 문제다.

https://draw-code-boy.tistory.com/203

[알고리즘] 백준 1725번: 히스토그램 (C++), 세그먼트 트리의 응용

다만, 문제에서 높이의 조건이 1,000,000,000까지라서 INF를 1,000,000,000 + 1로 define 해주었다.

 

[AC 코드]

#include <iostream>
#include <cmath>
#define MAX (100000 + 1)
#define INF 1000000000 + 1
#define ll long long
using namespace std;

ll sgTree[MAX * 4];
ll arr[MAX];
int n;

int minIdx(int a, int b) {
	return arr[a] < arr[b] ? a : b;
	//if (arr[a] == arr[b]) return min(a, b);
}

int sgInit(int start, int end, int node) {
	if (start == end) {
		return sgTree[node] = start;
	}

	int mid = (start + end) >> 1;
	return sgTree[node] = minIdx(sgInit(start, mid, node * 2), sgInit(mid + 1, end, node * 2 + 1));
}

int query(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 0;

	if (left <= start && end <= right) return sgTree[node];

	int mid = (start + end) >> 1;
	return minIdx(query(start, mid, node * 2, left, right), query(mid + 1, end, node * 2 + 1, left, right));
}

ll getMax(int start, int end) {
	int m = query(1, n, 1, start, end);

	ll area = (ll)(end - start + 1) * (ll)arr[m];

	if (start <= m - 1) {
		ll temp = getMax(start, m - 1);
		if (area < temp) {
			area = temp;
		}
	}

	if (end >= m + 1) {
		ll temp = getMax(m + 1, end);
		if (area < temp) {
			area = temp;
		}
	}

	return area;
}

int main() {
	arr[0] = INF;
	while (1) {
		cin >> n;
		if (n == 0) break;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}
		sgInit(1, n, 1);

		cout << getMax(1, n) << '\n';
	}
	return 0;
}