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

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

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; } }

공유하기 글 요소 저작자표시

from http://circus7.tistory.com/19 by ccl(A) rewrite - 2021-11-02 11:01:21