문제 링크: https://www.acmicpc.net/problem/6549

원 출처: University of Ulm Local Contest > University of Ulm Local Contest 2003

H번 histogram이다. 위 링크에서 문제, 답안, 제시된 테스트 케이스들과 그에 따른 출력 결과를 확인할 수 있다.

문제 상황

위와 같이 히스토그램, 즉 너비 1의 직사각형 여러 개가 서로 붙어있으면서 아래쪽으로 정렬되어 있는 도형이 주어진다. 이때 히스토그램에서 찾을 수 있는 가장 넓이가 큰 직사각형을 찾아라.

입력

Each Line(each test case): 직사각형의 수 \(n (1≤n≤100,000)\)과 히스토그램의 각 직사각형의 높이 \(h_i (0≤h_i≤1,000,000,000 인 정수)\)가 순서대로 주어진다. 마지막 줄 입력을 0으로 받아 종료.

ex)

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

출력

Each Line(each test case): 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력

ex)

8
4000

1. 접근

처음 문제를 봤을 때 그렇게 어렵지 않을 것 같은데 처음 풀게되는 Platinum V 문제여서 심상치 않음을 느끼긴 했다.

다양한 방법으로 구현해봤지만 역시 예상했던대로 모든 테스트 케이스를 커버하지 못했다…… 어쩔수 없이 (내 능력의 한계로) 알고리즘 분류에 ‘Stack’, ‘Divide and Conquer’가 있다는 것을 참고해 이 방법들로 풀어야겠다고 생각했다.

테스트케이스를 입력줄 별로 처리해야하므로 우선 아래와 같이 구현하였다.

C++17로 구현하였다.

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;

    for(cin>>n; n; cin>>n){         // 0 입력시 종료.
        int h; long long ans=0LL;   // n*h는 최대 10^14이므로 int8_t 필요.
        
        for(int i=0;i<n;++i){
            cin>>h;
            //process somehow
        }
        
        cout<<ans<<'\n';
    }
    
    return 0;
}

2. Stack

스택으로 뭘 어쩌란 말일까. 하지만 뒤집어 생각하면 임시로 저장해야 할 데이터들이 굳이 배열, 리스트 또는 큐 등의 자료구조가 아니어도 되며, LIFO 방식의 접근이면 충분하다는 뜻이다. 사실 그래도 여전히 무슨 정보를 저장해야 할 지 잘 모르겠다.

2-1. 문제연구

어쩔 수 없다. 예시를 가지고 나 스스로는 어떻게 풀어내는지 한번 보자. 앞서 문제상황에서 주어진 예시처럼 왼쪽부터 높이가 2,1,4,5,1,3,3 인 너비 1의 7개의 직사각형이 붙어있는 형태의 히스토그램으로 생각하자.

분할정복이 아닌 이상 생각할 수 있는 가장 일반적인 방법은 결국 순차탐색이다.

1. 1번째 직사각형까지 탐색시 (h=2)
   • 높이 2 × 너비 1 = 2 (확장가능)
   • 높이 1 × 너비 1 = 1 (확장가능)
2. 2번째 직사각형까지 탐색시 (h=1)
   • 높이 2 × 너비 1 = 2 (확장불가)
   • 높이 1 × 너비 2 = 2 (확장가능)
3. 3번째 직사각형까지 탐색시 (h=4)
   • 높이 1 × 너비 2 = 3 (확장가능)
   • 높이 4 × 세로 1 = 4 (확장가능)
   • 최대 4이다.
4. 4번째 직사각형까지 탐색시 (h=5)
   • 높이 1 × 너비 4 = 4 (확장가능)
   • 높이 4 × 세로 2 = 8 (확장가능)
   • 높이 5 × 세로 1 = 5 (확장가능)
   • 최대 8이다.
5. 5번째 직사각형까지 탐색시 (h=1)
   • 높이 1 × 너비 5 = 5 (확장가능)
   • 높이 4 × 세로 2 = 8 (확장불가)
   • 높이 5 × 세로 1 = 5 (확장불가)
   • 최대 8이다.
6. 6번째 직사각형까지 탐색시 (h=3)
   • 높이 1 × 너비 6 = 6 (확장가능)
   • 높이 4 × 세로 2 = 8 (확장불가)
   • 높이 3 × 세로 1 = 3 (확장가능)
   • 최대 8이다.
7. 7번째 직사각형까지 탐색시 (h=3)
   • 높이 1 × 너비 7 = 7 (확장가능)
   • 높이 4 × 세로 2 = 8 (확장불가)
   • 높이 3 × 세로 2 = 6 (확장가능)
   • 최대 8이다.

높이가 4인 두번째 직사각형 다음에 4보다 높은 직사각형이 오면서 높이 4에 폭이 1보다 큰 직사각형을 만들수 있게되었다. 하지만 그 다음에 4보다 작은 직사각형이 오면서 높이 4인 직사각형의 폭은 2가 최대임이 확정되었다.

다시말해 증가하는 구간에서는 답이 될 수 있는 새로운 높이 후보들이 나오게 되고, 감소하는 구간에서는 이 후보들의 최대 너비가 확정된다.

2-2. 문제 해결 전략

다시말해 증가하는 구간에서는 답이 될 수 있는 새로운 높이 후보들이 나오게 되고, 감소하는 구간에서는 이 후보들의 최대 너비가 확정된다.

앞서 이와 같이 언급한 것에 착안하여, 대충 아래와 같은 방식으로 높이를 입력받아 스택에 저장하여 처리하면 될 것 같다.

• 반복문으로 n회 높이를 입력 받는다.
  1. 현재 입력받은 높이가 stack top의 높이보다 증가했으면 스택에 쌓는다.
  2. stack top의 높이보다 감소했으면 현재 높이가 stack top보다 높게 될때까지 pop하면서 넓이를 계산한다.

위 방식을 이용해 앞서 다룬 예시를 다시 풀어보자.

1. 1번째 직사각형까지 탐색시 (h=2)
   • stack:[2]
   • ans=0
2. 2번째 직사각형까지 탐색시 (h=1)
   • 높이 2 × 너비 1 = 2 (pop)
   • 최대 2
   • stack에는 1을 남김 (처음부터 1로 시작하는 경우 고려)
   • stack:[1]
   • ans=2
3. 3번째 직사각형까지 탐색시 (h=4)
   • stack:[1,4]
   • ans=2
4. 4번째 직사각형까지 탐색시 (h=5)
   • stack:[1,4,5]
   • ans=2
5. 5번째 직사각형까지 탐색시 (h=1)
   • 높이 5 × 너비 1 = 5 (pop)
   • 높이 4 × 너비 2 = 8 (pop)
   • 최대 8
   • stack에는 1을 남김 (3번째부터 1로 시작하는 경우 고려)
   • stack:[1,1]
   • ans=8
6. 6번째 직사각형까지 탐색시 (h=3)
   • stack:[1,1,3]
   • ans=8
7. 7번째 직사각형까지 탐색시 (h=3)
   • stack:[1,1,3,3]
   • ans=8
8. 마무리
   • 높이 3 × 너비 2 = 6 (pop)
   • 높이 3 × 너비 1 = 3 (pop)
   • 높이 1 × 너비 4 = 4 (pop)
   • 높이 1 × 너비 7 = 7 (pop)
   • 최대 8
   • stack:[]
   • ans=8

2-3. 구현

앞서 시도해 본 방법 그대로, 높이를 n회 입력받으면서 현재 높이를 stack top과 비교해 높으면 stack에 쌓고, 낮으면 하나씩 꺼내서 계산해보는 과정을 잘 구현하였다.

for(cin>>n; n; cin>>n){         // 0 입력시 종료.
    stack<int> stk;
    int h; long long ans=0LL;   // n*h는 최대 10^14이므로 int8_t 필요.
        
    for(int i=0;i<n;++i){
        for(cin>>h; !stk.empty()&&h<stk.top(); stk.pop()){
            //process somehow
        }
        stk.push(h);
    }
    for(;!stk.empty();stk.pop())
        //process somehow
        
    cout<<ans<<'\n';
}

이제 계산하는 과정만 구현하면 되는데, 너비를 계산하기위해 stack에 높이를 저장할때 몇번째 직사각형인지 인덱스도 저장해야겠다. 그래서 pair의 first에 높이, second에 인덱스를 저장하여, 스택에는 pair<int,int>를 저장하도록 수정하였다.

int index라는 변수를 도입했는데, stk.top().second를 매번 참조하는게 번거롭기도 하고 저장할 필요성이 있어서 도입했을 뿐이다.

for(cin>>n; n; cin>>n){         // 0 입력시 종료.
    stack<pair<int,int>> stk;
    int h; long long ans=0LL;   // n*h는 최대 10^14이므로 int8_t 필요.
        
    for(int i=0;i<n;++i){
        int index = i;
        for(cin>>h; !stk.empty()&&h<stk.top().first; stk.pop()){
            index=stk.top().second;
            ans=max(ans,(long long) stk.top().first*(i-index));
        }
        stk.push(make_pair(h,index));
    }
    for(;!stk.empty();stk.pop())
        ans=max(ans,(long long) stk.top().first*(n-stk.top().second));
        
    cout<<ans<<'\n';
}

우선 cin>>h는 무조건 n회 실행된다.

이후 현재높이h가 stk.top()보다 같거나 높은 경우를 살펴보자. 그럼 바로 stk.push(make_pair(h,index));가 실행되는데 index에는 i가 들어있으니 현재 직사각형의 인덱스가 들어가게 된다. 앞서 이야기 한대로 잘 되는 듯 싶다.

그렇다면 현재높이h가 stk.top()보다 낮은경우는 어떨까. 반복문의 조건이 맞아 실행이 되고, stk.top()에 대한 계산이 끝나면 stk.pop()가 실행된다. 계산하는 과정에 주목해야겠다.

결국 직사각형 영역 계산은 아래와 같다.

stk.top().first*(i-stk.top().second)

stk.top().first높이의 직사각형의 넓이를 구하고 있는데 이때 최대 너비는 stk.top().second부터 현재 직사각형의 인덱스 직전까지이다. (현재 직사각형의 높이부터가 stk.top().first보다 낮아져 더 넓어질수 없음이 확정되었기 때문에) 따라서 위와 같은 식으로 계산 되었다.

한편, 이렇게 계산이 이루어진 후에도 여전히 stk에 push가 되어야 한다. 어쨌든 입력받은 현재높이에서 시작하는 경우도 고려해야하기 때문이다. 여기서 인덱스가 현재 인덱스가 아닌 ‘마지막으로 pop한 인덱스’여야 최대 너비를 구할 수 있다.

앞선 예시에서 5번째 직사각형의 높이 1을 받고 ‘높이 5 × 너비 1 = 5’, ‘높이 4 × 너비 2 = 8’를 계산하고 pop한 이후를 생각해보자.

현재 높이 1을 5번째부터 시작할 수도 있지만, 그 이전에 3번째 4번째가 충분히 높기 때문에 3번째(index=stk.top().second)부터 시작할 수 있다. 물론 예시의 경우 높이 1은 첫번째부터 시작할 수 있겠지만, 일반화 시켜야 하니 2번째가 현재높이보다 낮았다면 stk.top().second가 최선이다.

(조금만 생각해보면 알 수 있다. 앞서 #2-2에서 ‘1로 시작하는 경우 고려’라며 stack에 1을 추가한 것에 주목하라)

2-4. 최종 코드

이제 합쳐주면 최종 코드가 완성된다. stack 헤더를 사용하였으니 이를 include해주는 전처리 지시문이 추가되었음에 유의하라.

#include <iostream>
#include <stack>
using namespace std;

int main(int argc, const char * argv[]){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;

    for(cin>>n; n; cin>>n){         // 0 입력시 종료.
        stack<pair<int,int>> stk;
        int h; long long ans=0LL;   // n*h는 최대 10^14이므로 int8_t 필요.
        
        for(int i=0;i<n;++i){
            int index=i;
            for(cin>>h;!stk.empty()&&h<stk.top().first;stk.pop()){
                index=stk.top().second;
                ans=max(ans,(long long) stk.top().first*(i-index));
            }
            stk.push(make_pair(h,index));
        }
        for(;!stk.empty();stk.pop())
            ans=max(ans,(long long) stk.top().first*(n-stk.top().second));
        
        cout<<ans<<'\n';
    }
    
    return 0;
}

제출 소스 확인하기

3. Divide and Conquer

BOJ에서는 본 문제가 ‘분할 정복’ 단계로 분류되어 있는만큼 분할정복으로 풀어보는 것도 의미가 있겠다. (다만 스택으로는 \(O(n)\)시간으로 풀 수 있어 스택이 더 빠르다.)

앞서 스택으로 푼 방법은 입력받는 그때그때마다 후보들을 추려 검사하고 확실히 정해졌는지 확인해 그 중 답만 찾아내고 아닌 것들을 버리는 탐욕적인 방식이었다. (스택은 후보들을 저장하는 방식일 뿐이었다.) 때문에 분할정복으로 접근하면 전혀 다른 방식으로 풀게 될 것 같다.

3-1. 문제 예시 연구

분할정복으로 접근할 때, 구간은 어떠한 기준으로, 어떻게 분할하고 어떤 조건을 검사하고 이를 다시 정복해야할까. 조금 깊이 생각해보면 알겠다만, 예시연구만한게 없다. 앞서 문제에 주어진 예시, 왼쪽부터 높이가 2,1,4,5,1,3,3 인 너비 1의 7개의 직사각형이 붙어있는 형태의 히스토그램을 생각하자.

3-1-1. 처음 접근했던 방법

내가 문제를 보자마자 어떻게 눈으로 풀까 생각했던 방법이다. 직사각형이 적어 가능하긴했다.

1. 높이가 1인 직사각형
   • 모든 직사각형 영역에서 높이 1이 가능하므로, 전체 너비인 7이 최대 너비
   • 높이 1 × 너비 7 = 7
2. 높이가 2인 직사각형
   • 첫번째 직사각형에서만 가능하다.
   • 다른 영역에선 이보다 높게 가능하므로 의미 없다.
   • 높이 2 × 너비 1 = 2
3. 높이가 3인 직사각형
   • 여섯번째, 일곱번째 직사각형에서 가능하다.
   • 다른 영역에선 이보다 높게 가능하므로 의미 없다.
   • 높이 3 × 너비 2 = 6
4. 높이가 4인 직사각형
   • 세번째, 네번째 직사각형에서 가능하다.
   • 높이 4 × 너비 2 = 8
5. 높이가 5인 직사각형
   • 네번째 직사각형에서만 가능하다.
   • 높이 5 × 너비 1 = 5
6. 높이가 6이상인 직사각형
   • 불가능

높이에 따른 직사각형의 최대너비를 생각하였다. 높이를 하나씩 높여가며 살펴보니, 최대너비가 되어줄 구간을 결국 구간의 최소값 또는 극소값(?)으로 나뉜다. 높이 4인 직사각형은 양쪽의 높이 1의 직사각형 덕에 그 너비가 제한되었다.

이 방법을 그대로 코드로 옮기는 건 무모한 짓이다. 하지만 뭔가 생각해볼 수 있을 것 같다.

3-1-2. 구간 내 최소값을 기준으로 분할하기

이번에도 예시로 살펴보자.

[2,1,4,5,1,3,3]에서 최소값은 두번째, 다섯번째의 1이다.

따라서 이 전 구간을 너비로 가지는 가장 큰 직사각형은 ‘높이 1 × 너비 7 = 7’의 직사각형이다. 이후 최소값에 따라 구간이 아래와 같이 분할될 수 있다.

[2] / [4,5] / [3,3]

[2] 구간에서 직사각형 최대 넓이는 2이다. [4,5] 구간은 [4] / [5]로 분해 될 수도 있다. 하지만 이 구간을 너비로 가지는 직사각형은 ‘높이 4 × 너비 2 = 8’이므로 여기서 8이 가장 크다. [3,3] 구간 역시 [3] /[3]으로 분해될 수 있지만, 이 구간을 너비로 가지는 직사각형은 ‘높이 3 × 너비 2 = 6’이므로 여기서 6이 가장 크다.

분할된 위 구간들을 다시 정복하는 과정에서 2, 8, 6 중 8이 가장 크며 이는 전 구간을 너비로 가지는 ‘높이 1 × 너비 7 = 7’의 직사각형보다 크므로 답은 8이 되어야 한다.

3-2. 문제해결 전략

앞서 살펴본 예시연구로부터 아래와 같은 문제해결전략을 찾아낼 수 있었다.

• 구간의 크기가 2 이상이면, 구간 내 최소값을 찾아 이를 기준으로 구간을 다시 둘로 분할한다.
• 구간의 크기가 1이면 해당 직사각형의 높이를 반환한다. (너비 1이니 높이가 곧 넓이.)
• 분할된 구간을 정복하는 과정에서 (구간 너비) × (구간 최소값)과 분할구간에서 구한 최대 넓이와 비교해 큰 것만 반환한다.

하지만 이 과정을 무식하게 구현했다가는 피본다. 가장 큰 문제는 주어진 구간마다 최소값을 찾아야 한다는 건데, 그때마다 일일이 순차탐색으로 최소값을 구하는건 말도 안 된다. 트리구조를 이용하는게 그나마 현실적인데, 익숙치 않아서 최대한 피하고자 하였다. 그다음으로 생각한 방법은 최소값으로 정렬이었다. 한번 정렬한 이후로 대소비교는 필요가 없고, 순차탐색하며 해당 범위내에 있는지 확인하면 최소값을 그냥 찾아낼 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool lowerHeight(pair<int,int> a, pair<int,int> b){ // 높이에 대한 오름차순 정렬을 위한 대소비교 함수
    return (a.first==b.first ? (a.second<b.second) : (a.first<b.first));
}

long long bigRect(vector<pair<int,int>> &h, int begin, int end){        // 분할 정복
    pair<int,int> min;
    for(vector<pair<int,int>>::iterator it=h.begin();it!=h.end();++it)  // 정렬된 벡터를 순차 탐색하며
        if(it->second>=begin && it->second<end){                        // 구간 내에 있는 원소 확인시 (구간 내 최소값이다.)
            min=*it;                                                    // 최소값으로 등록 후
            h.erase(it);                                                // 벡터에서 지워버린다.
            break;
        }

    long long ans = min.first*(end-begin);                              // 앞서 찾은 최소값을 바탕으로 해당 구간을 너비로 하는 최대 직사각형 넓이
    if(end-begin>1){
        long long tmp = bigRect(h,begin,min.second);                    // 해당 최소값보다 앞선 분할구간 확인
        if(tmp>ans) ans=tmp;
        tmp=bigRect(h,min.second+1,end);                                // 해당 최소값보다 뒤진 분할구간 확인
        if(tmp>ans) ans=tmp;
    }
    return ans;
}

int main(int argc, const char * argv[]){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;

    for(cin>>n; n; cin>>n){         // 0 입력시 종료.
        vector<pair<int,int>> rect;
        
        rect.reserve(n);
        for(int i=0;i<n;++i){
            int height;
            cin>>height;
            rect.push_back(make_pair(height,i));
        }
        
        sort(rect.begin(),rect.end(),lowerHeight);  // 높이에 대한 오름차순 정렬
        cout<<bigRect(rect,0,n)<<'\n';
    }
    
    return 0;
}

제출 소스 확인하기

여전히 어림도 없다. 정렬을 했어도 탐색 순서와 정렬 순서가 일치하지 않아 찾아내는데 시간이 너무 많이 걸린다.

3-3. 수정된 전략

앞선 쭉 연구해온 예시로 당장 위 코드를 실행한다고 생각해보면 분할도 너무 비대칭적일 뿐더러 (정렬을 사용해도 결국) 구간내 최소값을 찾는데 오랜 시간이 소모된다.

이런 방식을 포기하고, 깔끔히 이등분할 하기로 했다. 하지만 최대넓이의 직사각형은 얼마든지 이등분할된 구간 여러개를 거쳐서 존재할 수 있다. 사실 이때문에 처음에 이등분할을 포기했던 것이긴 하다. 그래서 다른 방법으로 이를 보완하였다.

주어진 분할구간의 중앙부터 시작하여 직사각형의 너비구간을 확장시켜나간다. 이때 당연히 높이는 구간내 최소값으로 조정해 나간다. 이렇게 하면 모든 구간에서 각자 가능한 높이들을 모두 검사하게된다. (처음에 전구간에서 시작해 분할해 나가기 때문에 분할 구간에 걸치는 경우도 검사하게 된다. 그럼에도 분할이 필요한건 분할구간에서 더 높은 높이가 가능한 경우도 계산해야하기 때문이다.)

long long solve(vector<long long>& h, int left, int right){
    if(left == right) return h[left];
    int lo = (left+right) >> 1;         // mid = (left+right)/2;
    int hi = lo+1;                      // 오른쪽 확장도 mid바로 다음부터 시작한다.
    long long res = max(solve(h, left, lo), solve(h, hi, right)); // Divide and Conquer
    long long height = min(h[lo], h[hi]);
    res = max(res, height<<1);
    while(left<lo || hi<right){         // 양 구간 끝에 도달할때까지 탐색
        height = (hi<right && (left==lo || h[lo-1]<h[hi+1])) // 오른쪽으로 확장할 조건.
            ? min(height, h[++hi])      // 너비구간 오른쪽으로 확장
            : min(height, h[--lo]);     // 너비구간 왼쪽으로 확장
        res = max(res, height*(hi-lo+1));//확장된 너비구간의 직사각형 최대넓이와 비교
    }
    return res;
}

\(O(n log(n))\)의 시간복잡도로 해결 가능했다.

3-4. 최종코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long long solve(vector<long long>& h, int left, int right){
    if(left == right) return h[left];
    int lo = (left+right) >> 1;         // mid = (left+right)/2;
    int hi = lo+1;                      // 오른쪽 확장도 mid바로 다음부터 시작한다.
    long long res = max(solve(h, left, lo), solve(h, hi, right)); // Divide and Conquer
    long long height = min(h[lo], h[hi]);
    res = max(res, height<<1);
    while(left<lo || hi<right){         // 양 구간 끝에 도달할때까지 탐색
        height = (hi<right && (left==lo || h[lo-1]<h[hi+1])) // 오른쪽으로 확장할 조건.
            ? min(height, h[++hi])      // 너비구간 오른쪽으로 확장
            : min(height, h[--lo]);     // 너비구간 왼쪽으로 확장
        res = max(res, height*(hi-lo+1));//확장된 너비구간의 직사각형 최대넓이와 비교
    }
    return res;
}

int main(int argc, const char *argv[]){
    ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
    int n;

    for(cin>>n; n; cin>>n){
        vector<long long> h;
        h.reserve(n);

        for(int i=0; i<n; ++i)
            cin>>h[i];
        
        cout<<solve(h, 0, n-1)<<'\n';
        h.clear();
    }
    return 0;
}

제출 소스 확인하기

4. Segment Tree

단순 분할정복으로 푸는데 어려움을 겪을때 세그먼트 트리를 도입해 최소값을 효율적으로 찾고자 했었다. 트리구조 사용에 익숙치 않아 다른 출처로부터 도움을 받았는데 설명은 나중에 써야겠다.

#include <iostream>
#include <algorithm>
#define MAX_N 100000

using namespace std;

int n, h[MAX_N + 1], seg[4 * MAX_N];

void init(int node, int x, int y){
    if(x == y) { seg[node] = x; return ; }

    int mid = (x + y) >> 1;
    init(node*2, x, mid);
    init(node*2+1, mid+1, y);
    if (h[seg[node*2]] <= h[seg[node*2+1]])
        seg[node] = seg[node*2];
    else
        seg[node] = seg[node*2+1];
}

int query(int lo, int hi, int node, int x, int y){
    if(y<lo || hi<x) return -1;
    if(lo<=x && y<=hi) return seg[node];
    int mid = (x + y) >> 1;
    int q1 = query(lo, hi, node*2, x, mid);
    int q2 = query(lo, hi, node*2+1, mid+1, y);
    if(q1==-1) return q2;
    if(q2==-1) return q1;
    return ((h[q1] <= h[q2]) ? q1 : q2);
}

long long sol(int lo, int hi){
    int m = query(lo, hi, 1, 0, n-1);
    long long res = (long long) (hi-lo+1)*h[m];
    if(lo <= m-1) res = max(res, sol(lo, m-1));
    if(m+1 <= hi) res = max(res, sol(m+1, hi));
    return res;
}

int main(int argc, const char *argv[]){
    ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

    for(cin>>n; n; cin>>n){
        for(int i=0; i<n; ++i)
            cin>>h[i];
        init(1, 0, n-1);
        cout<<sol(0, n-1)<<'\n';
    }
    return 0;
}

제출 소스 확인하기