[백준] 1725 : 히스토그램

풀이실패ㅠㅠ

 

import java.util.*;

public class Main {
	public static long histogram(long[] arr , int s , int e) {
        if(s>e) return -1;
        if(s==e) return arr[s]*1;

        int mid = (s+e)/2;
        //왼, 오 답 각각 비교해서 리턴
        long result  = Math.max(histogram(arr, s, mid),histogram(arr, mid+1, e));

        long w = 1; //연속값들의 합 
        long h = arr[mid] ; //최소 높이
        int l = mid; //왼쪽
        int r = mid;
        while(r-l < e - s) {
            long p = (l > s) ? Math.min(h, arr[l - 1]) : -1;
            int leftIdx = (p == -1) ? 0 : l-1;
            long q = (r < e) ? Math.min(h, arr[r + 1]) : -1;
            int rightIdx = (q == -1) ? 0 : r+1;
            if(p > q) { //왼쪽이 더 클때 
                h = p;
                ++w;
                l--;
            }else{
                h = q;
                ++w;
                r++;
            }
            result = Math.max(result, h*w);
        }
        return result;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[100001];
        for(int i=1; i<=n; i++) {
            arr[i] = sc.nextInt();
        }
        long result = histogram(arr, 1, n); 
        System.out.println(result);
    }
}