[백준oj] 6549번 히스토그램에서 가장 큰 직사각형

www.acmicpc.net/problem/6549

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

---

 

 

이문제는 아래의 문제와 동일하게 세그먼트트리, 분할정복을 이용해 풀면된다.

12846번 무서운 아르바이트

[백준oj] 12846번 무서운 아르바이트

 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
long long tree[4 * 100001];
long long arr[100001];

void init(int st, int end, int node) {
	if (st == end) {
		tree[node] = st;
		return;
	}

	int middle = (st + end) >> 1;
	init(st, middle, node * 2);
	init(middle + 1, end, node * 2 + 1);
	if (arr[tree[node * 2]] <= arr[tree[node * 2 + 1]]) {
		tree[node] = tree[node * 2];
	}
	else {
		tree[node] = tree[node * 2 + 1];
	}
}

long long min(int st, int end, int node, int l, int r) {
	if (r < st || end < l) {
		return -1;
	}

	if (l <= st && end <= r) {
		return tree[node];
	}
	
	int middle = (st + end) >> 1;
	long long m1 = min(st, middle, node * 2, l, r);
	long long m2 = min(middle + 1, end, node * 2 + 1, l, r);
	if (m1 == -1) {
		return m2;
	}
	else if (m2 == -1) {
		return m1;
	}
	else {
		return arr[m1] < arr[m2] ? m1 : m2;
	}
}

long long solve(int l, int r,int n) {
	long long mini = min(0, n - 1, 1, l, r);
	long long result = (long long)(r - l + 1)*(arr[mini]);

	if (l <= mini - 1) {
		long long temp = solve(l, mini - 1, n);
		if (temp > result) {
			result = temp;
		}
	}
	if (mini + 1 <= r) {
		long long temp = solve(mini + 1, r, n);
		if (temp > result) {
			result = temp;
		}
	}
	return result;
}

int main() {

	while (true) {
		int n;
		cin >> n;
		if (n == 0) {
			break;
		}
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}
		init(0, n - 1, 1);
		cout << solve(0, n - 1, n) << "\n";
	}

	return 0;
}