백준 6549 : 히스토그램에서 가장 큰 직사각형 (C++)

6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net)

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

 

#include<bits/stdc++.h>
#define MAX 1000000007
#define INF 2000000000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dt[3] = { -1,0,1 };
/*
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };

int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };
*/
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll v[100001];
int n;
ll func(int start,int end) {
    if (end < start) return 0;
    else if (start == end) return v[start];
    else if (start + 1 == end) {
        return max(min(v[start], v[end]) * 2, max(v[start], v[end]));
    }

    int mid = (start + end) / 2;
    ll len = 1, mn = v[mid];
    ll mx = max(max(func(start, mid - 1), func(mid + 1, end)),mn*len);
    int low = mid - 1, top = mid + 1;
    
    while (start <= low || top <= end) {
        if (v[top] == 0 && v[low] == 0) break;
        if (low < start) {
            mn = min(mn, v[top++]);
        }
        else if (top > end) {
            mn = min(mn, v[low--]);
        }
        else {
            if (v[top] > v[low]) {
                mn = min(mn, v[top++]);
            }
            else if(v[top] <= v[low]){
                mn = min(mn, v[low--]);
            }
        }
        mx = max(mx, ++len * mn);
    }
    return mx;
}
int main() {
    init();
    while (1) {
        cin >> n;
        if (n == 0) return 0;

        for (int i = 1; i <= n; i++) cin >> v[i];
        cout << func(1, n) << "\n";
    }
}