[BOJ] 1725 히스토그램 (JAVA)

https://www.acmicpc.net/problem/1725

1725번: 히스토그램

세그먼트 트리 문제입니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static final int INF = Integer.MAX_VALUE;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int[] input, result;

    public static void main(String[] args) throws Exception {

        N = Integer.parseInt(br.readLine());

        input = new int[N + 1];
        result = new int[N * 4];
        for (int i = 1; i <= N; i++) {
            input[i] = Integer.parseInt(br.readLine());
        }
        make(1, N, 1);

        System.out.print(getMaxWidth(1, N));

    }

    static int select(int startIndex, int endIndex, int treeIndex, int startRange, int endRange) {

        if(endIndex < startRange || endRange < startIndex) return INF;

        if(startRange <= startIndex && endIndex <= endRange) return result[treeIndex];

        int midIndex = (startIndex + endIndex) / 2;
        int left  = select(startIndex, midIndex, treeIndex * 2, startRange, endRange);
        int right = select(midIndex + 1, endIndex, treeIndex * 2 + 1, startRange, endRange);

        if(left == INF) return right;
        else if(right == INF) return left;
        return input[left] < input[right] ? left : right;

    }

    static long getMaxWidth(int startIndex, int endIndex) {

        long maxWidth = 0;
        int minIndex = select(1, N, 1, startIndex, endIndex);

        maxWidth = (long) (endIndex - startIndex + 1) * (long) input[minIndex];

        if(startIndex <= minIndex - 1) maxWidth = Math.max(maxWidth, getMaxWidth(startIndex, minIndex - 1));

        if(minIndex + 1 <= endIndex) maxWidth = Math.max(maxWidth, getMaxWidth(minIndex + 1, endIndex));

        return maxWidth;

    }

    static int make(int startIndex, int endIndex, int treeIndex) {

        if(startIndex == endIndex) return result[treeIndex] = startIndex;

        int midIndex = (startIndex + endIndex) / 2;
        int left  = make(startIndex, midIndex, treeIndex * 2);
        int right = make(midIndex + 1, endIndex, treeIndex * 2 + 1);

        return result[treeIndex] = input[left] < input[right] ? left : right;

    }
	
}