Largest Rectangle

Problem

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

Summary

히스토그램에서 모든 막대의 너비는 1이고, 높이는 hi일 때
모든 막대 x에 대해서, x를 높이로 하면서 만들 수 있는 가장 큰 직사각형을 찾기
(1 ≤ n ≤ 100,000) h1, …, hn (0 ≤ hi ≤ 1000000000)

Idea


static long largest(int s, int e) {
    int x = e -s +1;
    int idx = query(s, e);
    long size = x * arr[idx];
    
    if (s <= idx-1) {
        long t = largest(s, idx-1);
        if (size < t) {
            size = t;
        }
    }
    if (idx+1 <= e) {
        long t = largest(idx+1, e);
        if (size < t) {
            size = t;
        }
    }
    return size;
}