[알고리즘] 백준 > #2104. 부분배열 고르기

문제링크

백준 #2104. 부분배열 고르기

풀이방법

와 분할정복 풀고싶어서 분할정복으로 검색한 문제인데 보자마자 히스토그램 문제가 생각나서 아주 쉽게 문제를 풀 수 있었다...!!!

큰 흐름은 히스토그램과 아아아아주 똑같다. 조금 다른 부분이 있다면 sum(A[i], ..., A[j])를 세그먼트트리를 사용하지 않고 구간합 배열을 사용했다는 점! 풀이를 이끌 키 아이디어도 히스토그램 문제와 똑같다! "가장 낮은 index가 포함되었을 때 가장 큰 점수를 구했고, 이제 얘를 뺐을 때 가장 큰 점수들을 구해볼게~" 이다. 그러면 문제 해결~

코드

import java.util.*;
public class BOJ2104 {

    static int n;
    static int[] a;
    static long[] preSum;
    static long result = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        a = new int[n + 1];
        a[0] = 0;
        preSum = new long[n + 1];
        preSum[0] = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            preSum[i] = preSum[i - 1] + a[i];
        }

        searchMaxScore(1, n);

        System.out.print(result);
    }

    private static void searchMaxScore(int i, int j) {
        int minScoreIndex = j;
        for (int k = i; k < j; k++) {
            if (a[minScoreIndex] > a[k]) minScoreIndex= k;
        }

        long score = (preSum[j] - preSum[i - 1]) * a[minScoreIndex];
        if (result < score) result = score;

        if (i <= (minScoreIndex - 1)) searchMaxScore(i, minScoreIndex - 1);
        if ((minScoreIndex + 1) <= j) searchMaxScore(minScoreIndex + 1, j);
    }
}