[백준] 히스토그램에서 가장 큰 직사각형 6549번 - java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = null;
		while((line = br.readLine()) != null) {
			StringTokenizer st = new StringTokenizer(line, " ");
			int n = Integer.parseInt(st.nextToken());
			if(n == 0) return;
			h = new long[n];
			for(int i = 0; i < n; i++) {
				h[i] = Long.parseLong(st.nextToken());
			}
			long ret = solve(0, n - 1);
			System.out.println(ret);
		}
	}

	private static long[] h;
	private static long solve(int left, int right) {
		if(left == right) return h[left];
		
		int mid = (left + right) / 2;
		
		long ret = Math.max(solve(left, mid), solve(mid + 1, right));
		
		int lo = mid, hi = mid + 1;
		long height = Math.min(h[lo], h[hi]);
		ret = Math.max(ret, height * 2);
		
		while(left < lo || hi < right) {
			if(hi < right && (lo == left || h[lo - 1] < h[hi + 1])) {
				hi++;
				height = Math.min(height, h[hi]);
			} else {
				lo--;
				height = Math.min(height, h[lo]);
			}
			
			ret = Math.max(ret, height * (hi - lo + 1));
		}
		
		return ret;
	}
}