[[problem:FENCE]]

분할정복알고리즘으로..

중앙을 기준으로 왼쪽부분, 오른쪽부분 사각형의 최대 넓이
중앙에서 퍼져나가는 사각형의 최대넓이.. 이렇게 3가지를 비교해서 답을 구하는 방식으로 풀었습니다.

알고리즘 문제 해결 전략의 답안 소스를 봐도 제 소스랑 다른바가 없던데.. 왜 오답이 나는지 잘 모르겠네요 ㅠㅠ

#include<iostream>
    
using namespace std;

int length;
int height[20001]={0,};

int process(int x,int y)
{
    int mid=(x+y)/2;

    if(y-x==1 || y==x) 
    {
        if(height[x]>height[y]) return height[y]*(y-x+1);
        return height[x]*(y-x+1);
    }

    int left=process(x,mid);
    int right=process(mid+1,y);

    int i,j;
    int min=30000; int max=height[mid];

    for(i=mid,j=mid;i>=x,j<=y;)
    {
        if(height[i-1] > height[j+1]) i--;
        else j++;

        if(min>height[i]) min=height[i];
        if(min>height[j]) min=height[j];
        if(max<min*(j-i+1)) max=min*(j-i+1);

        
    }

    if(left>right) right=left;

    if(right>max) return right;
    else return max;
}

int main( )
{
    int T;
    for(cin >> T;T--;){
    
        cin >> length;

        for(int i=1;i<=length;i++) scanf("%d",&height[i]);

        cout << process(1,length) << endl;

    }
    return 0;   
}