[c언어/c++] 울타리 잘라내기 - FENCE 분할정복

너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다. 판자의 너비는 모두 1이라고 가정합니다.

문제 링크 - https://algospot.com/judge/problem/read/FENCE

#include<stdio.h>

#include<memory.h>
#include <algorithm> 
using namespace std;
int num;
int h[30000];

int area(int,int);

int main(){
 
 int loop;

 scanf("%d",&loop);

 for(int i = 0 ; i < loop ; i++){
  
  num = 0;
  memset(h,0,sizeof(h));

  scanf("%d",&num);

  for(int i = 0 ; i < num ; i++) scanf(" %d",&h[i]);

  printf("%d\n",area(0,num));

 }

 return 0;
}


int area(int start,int end){
 
 if(start == end) return h[start];

 int mid = (start + end) / 2;

 int result = 0;

 result = max(area(start,mid),area(mid+1,end));
 
 int min_h = min(h[mid],h[mid+1]);

 result = max(result, min_h * 2);

 int l = mid;
 int r = mid + 1;
 while(start < l || r < end ){
  if(l == start || h[l-1] < h[r+1]){
   r++;
   min_h = min(min_h,h[r]);
  }
  else{
   l--;
   min_h = min(min_h,h[l]);
  }

  result = max(result, min_h * ( r- l +1));
 }
 
 /*
 for(int left = start ; left < end ; left++){
  int min_h = h[left];
  for(int right = left ; right < end ; right++){
   min_h = min(min_h,h[right]);
   result = max((right -left + 1)*min_h,result);
  }
 }
 */
 
 return result;
}