1725번 히스토그램

문제 링크

히스토그램

문제 풀이

FENCE와 완전 같은 문제이다.

구현

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
using ll = long long;

ll N;
vector<ll> A(100000);

ll solve(ll left, ll right) {
    if (left == right) return A[left];

    ll mid = (left + right) / 2;
    ll ret = max(solve(left, mid), solve(mid+1,right));

    ll minValue = min(A[mid], A[mid+1]);

    ret = max(ret, 2 * minValue);
    int low = mid, high = mid + 1;
    
    while (left < low || high < right) {
        if (left < low && (right == high || A[low-1] > A[high+1])) {
            --low;
            minValue = min(minValue, A[low]);
        }
        else {
            ++high;
            minValue = min(minValue, A[high]);
        }
        ret = max(ret, (high - low + 1) * minValue);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    cout << solve(0, N-1);
    return 0;
}