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

#include <iostream>
#include <algorithm>
#include <vector>
 
long long n = 0;
std::vector<long long> vec = {};
 
long long calculate(long long left, long long right)
{
    long long mid = (left + right) / 2;
    long long midArea = vec[mid];
    long long height = vec[mid];
    long long l = mid - 1;
    long long r = mid + 1;
 
    if (left + 1 >= right) 
    {
        return midArea;
    }
 
    while (l > left || r < right) 
    {
 
        if (l <= left || (r < right && vec[l] <= vec[r])) 
        {
            height = std::min(vec[r++], height);
        }
 
        else 
        {
            height = std::min(height, vec[l--]);
        }
 
        long long width = r - 1 - l;
        midArea = std::max(midArea, width * height);
    }
 
    return std::max(midArea, std::max(calculate(left, mid), calculate(mid, right)));
}
 
int main() 
{
    while (true) 
    {
        std::cin >> n;
 
        if (n == 0) 
        {
            break;
        }
 
        vec = std::vector<long long>(n + 2);
 
        for (int i = 1; i <= n; ++i) 
        {
            std::cin >> vec[i];
        }
 
        std::cout << calculate(0, n + 1) << "\n";
    }
 
    return 0;
}

중간값을 이용해서 양옆으로 분할해나가면서 푸는 문제

처음부터 이건 어떻게 푸는 거지... 이랬다

알고리즘 쉬운 것만 풀다가 다시 어려운 걸 풀라니까 정말 헷갈리더라