[백준][BOJ-1725][자바] 히스토그램

www.acmicpc.net/problem/1725

1725번: 히스토그램

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] height = new int[N];
		
		for(int i=0; i<N; i++) {
			height[i] = Integer.parseInt(br.readLine());
		}
		
		System.out.println(histogram(0,N,height));
	}
	
	public static int histogram(int left, int right, int[] height) {
		if(left == right) return 0;
		if(left+1 == right) return height[left];
		
		int mid = (left+right)/2;
		int result = Math.max(histogram(left, mid, height), histogram(mid, right, height));	// 각 양쪽 구간의 최댓값
		
		// 양쪽 구간에서 걸쳐 있는 답을 찾음
		int w =1, h = height[mid], l = mid, r = mid;
		while(r-l+1 < right-left) {
			int p = l>left ? Math.min(h, height[l-1]) : -1; // 왼쪽으로 확장했을 경우의 높이
			int q = r<right-1 ? Math.min(h, height[r+1]) : -1;	// 오른쪽으로 확장했을 경우의 높이
			
			// 더 높은(같은) 높이를 가진 쪽으로 확장
			if(p>=q) {
				h = p;
				l--;
			}
			else {
				h = q;
				r++;
			}
			
			//최댓값 갱신
			result = Math.max(result, ++w*h);
		}
		
		return result;
	}
}