백준 6549번

원본 : www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

 

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Stack;

public class Main {

	public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
	public static long maxArea = 0;
	
	public static void main(String[] args) throws Exception {
		while (true) {
			maxArea = 0;
			String str = reader.readLine();
			
			if (str.equals("0")) {
				break;
			} else {
				long arr[] = Arrays.stream(str.split(" ")).mapToLong(Long::parseLong).toArray();
				Stack<Integer> stack = new Stack<>();
				
				for (int i = 1; i <= arr[0]; i++) {
					if (stack.isEmpty()) {
						stack.add(i);
					} else {
						if (arr[stack.peek()] <= arr[i]) {
							stack.add(i);
						} else {
							while (true) {
								int right = i - 1;
								int left = 1;
								
								if (stack.isEmpty() || arr[stack.peek()] <= arr[i]) {
									break;
								} else {
									long value = arr[stack.pop()];
									
									if (!stack.isEmpty()) {
										left = stack.peek() + 1;
									}
									
									long area = value * (right - left + 1);
									
									if (area > maxArea) {
										maxArea = area;
									}
								}
							}
							stack.add(i);
						}
					}
				}
				
				if (!stack.isEmpty()) {
					while (true) {
						int right = (int)arr[0];
						int left = 1;
						
						if (stack.isEmpty()) {
							break;
						} else {
							long value = arr[stack.pop()];
							
							if (!stack.isEmpty()) {
								left = stack.peek() + 1;
							}
							
							long area = value * (right - left + 1);
							
							if (area > maxArea) {
								maxArea = area;
							}
						}
					}
				}
			}
			writer.write(maxArea + "\n");
		}
		
		writer.flush();
	}
	
}